pengantar
Tantangan ini serupa dengan masalah Project Euler . Saya datang dengan itu karena saya memainkan permainan papan sederhana yang menipu dan tidak dapat menghasilkan solusi yang efisien untuk menjawab pertanyaan sederhana tentang mekanismenya.
Quarto adalah varian yang menyenangkan dari 4 berturut-turut. Ini dimainkan di papan 4 oleh 4 dengan 16 lagu unik (tidak ada lagu yang digandakan). Setiap belokan setiap pemain menempatkan 1 buah di papan tulis. Setiap bagian memiliki 4 karakteristik biner (pendek / tinggi, hitam / putih, persegi / bundar, berongga / padat). Tujuannya adalah untuk membuat empat berturut-turut, baik secara horizontal, vertikal atau sepanjang 2 diagonal, untuk salah satu dari empat karakteristik tersebut! Jadi 4 keping hitam, 4 keping putih, 4 keping tinggi, 4 keping pendek, 4 keping persegi, 4 keping bundar, 4 keping berongga atau 4 keping solid.
Gambar di atas menunjukkan permainan yang sudah selesai, ada empat berturut-turut karena 4 buah persegi.
Tantangan
Di Quarto, beberapa pertandingan mungkin berakhir seri.
Jumlah total posisi akhir yang mungkin adalah 16!
, sekitar 20 triliun.
Berapa banyak posisi akhir yang diundi?
Aturan
Solusinya harus berupa program yang menghitung dan menampilkan jumlah posisi akhir yang diundi. Jawaban yang benar adalah
414298141056
Anda hanya dapat menggunakan informasi tentang aturan permainan yang telah dideduksi secara manual (tidak ada bukti bantuan komputer).
Penyederhanaan matematis dari masalah diperbolehkan, tetapi harus dijelaskan dan dibuktikan (secara manual) dalam solusi Anda.
Pemenangnya adalah yang memiliki solusi paling optimal dalam hal waktu berjalan CPU.
Untuk menentukan pemenang, saya akan menjalankan setiap solusi tunggal dengan waktu berjalan yang dilaporkan kurang dari 30m pada MacBook Pro 2,5 GHz Intel Core i7 dengan 16 GB RAM .
Tidak ada poin bonus untuk datang dengan solusi yang juga berfungsi dengan ukuran papan lainnya. Meskipun itu akan menyenangkan.
Jika berlaku, program Anda harus mengkompilasi dalam 1 menit pada perangkat keras yang disebutkan di atas (untuk menghindari penyalahgunaan optimasi kompiler)
Celah default tidak diizinkan
Pengajuan
Silakan kirim:
- Kode atau tautan github / bitbucket ke kode.
- Keluaran kode.
- Waktu berjalan yang diukur secara lokal
- Penjelasan tentang pendekatan Anda.
Batas waktu
Batas waktu pengiriman adalah 1 Maret, jadi masih banyak waktu.
Jawaban:
C: 414298141056 hasil imbang ditemukan dalam waktu sekitar
52,5 menit.Hanya pencarian mendalam-pertama sederhana dengan tabel transposisi sadar simetri. Kami menggunakan simetri atribut di bawah permutasi dan simetri dihedral 8 kali lipat dari papan.
Skor terukur (@wvdz):
Skor (pengguna + sistem): 1m35.727s
sumber
-O3 -march=native
dan mendapat 1m48 di mesin saya. (CC @wvdz)Java, 414298141056 draw, 23m42.272s
Saya harap itu tidak disukai untuk memposting solusi untuk tantangan sendiri, tetapi alasan saya memposting tantangan ini di tempat pertama adalah bahwa itu membuat saya gila bahwa saya tidak bisa datang dengan solusi yang efisien sendiri. Usaha saya yang terbaik akan membutuhkan waktu berhari-hari untuk diselesaikan.
Setelah mempelajari jawaban user1502040 , saya benar-benar berhasil memodifikasi kode saya untuk berjalan dalam waktu yang agak masuk akal. Solusi saya masih sangat berbeda, tetapi saya mencuri beberapa ide:
Perbedaan utama antara solusi ini dan user1502040 adalah bahwa saya tidak menggunakan tabel Zobrist, tetapi representasi kanonik dari sebuah papan, di mana saya menganggap setiap papan memiliki 48 kemungkinan transposisi atas karakteristik (2 * 4!). Saya tidak memutar atau memindahkan seluruh papan, tetapi hanya karakteristik dari bagian-bagiannya.
Ini adalah yang terbaik yang bisa saya pikirkan. Ide untuk optimasi yang jelas atau kurang jelas sangat disambut!
Skor terukur:
Skor (pengguna + sistem): 23m42.272s
sumber