Teka-teki delapan ratu
Teka-teki delapan ratu meminta delapan ratu di papan catur tanpa ada dua ratu yang saling menyerang. Komposer soal catur Max Bezzel menerbitkannya pada tahun 1848, dan teka-teki ini menjadi contoh pertama yang klasik untuk pencarian backtracking.
Teka-teki catur dari tahun 1848
Max Bezzel, komposer soal catur asal Jerman, mengajukan teka-teki ini di sebuah jurnal catur Berlin pada tahun 1848. Franz Nauck menerbitkan semua 92 solusi pada tahun 1850 dan mengajukan pertanyaan yang sama untuk papan yang lebih besar. Carl Friedrich Gauss mengikuti teka-teki ini dengan penuh minat dan membahasnya dalam surat-suratnya.
Satu ratu per baris dan kolom
Delapan ratu yang tidak saling menyerang harus berada di delapan baris yang berbeda dan delapan kolom yang berbeda. Jadi sebuah solusi adalah acakan angka 1 sampai 8, yaitu sebuah permutasi, dengan satu aturan tambahan: tidak boleh ada dua ratu di diagonal yang sama. Dari 40.320 permutasi, hanya 92 yang lolos.
Backtracking (runut-balik)
Backtracking membangun solusi sepotong demi sepotong dan mundur begitu menemui jalan buntu. Untuk ratu: letakkan ratu di petak aman pertama pada baris berikutnya, dan jika sebuah baris tidak punya petak aman, kembali ke baris di atasnya dan geser ratu di sana maju. Pada tahun 1972 Edsger Dijkstra memakai teka-teki ini untuk menjelaskan pemrograman terstruktur dengan pencarian persis seperti ini.
Simetri
Putar papan seperempat putaran, atau cerminkan, dan sebuah solusi tetap menjadi solusi. Itu memberi hingga delapan versi dari setiap solusi. Ke-92 solusi terbagi menjadi 12 keluarga seperti itu: sebelas dengan 8 anggota, dan satu dengan hanya 4, karena solusi itu tetap sama setelah diputar setengah putaran.
Masalah n-ratu
Pada papan n×n pertanyaannya sama, dengan n ratu. Ada solusi untuk setiap n mulai dari 4, dan jumlahnya tumbuh cepat: 2 untuk 4×4, 92 untuk 8×8, dan 14.200 untuk 12×12. Belum diketahui rumus untuk jumlah itu; nilai rekornya berasal dari pencarian komputer berskala besar.
Coba di PictorX
Buka Delapan Ratu dan klik sebuah petak untuk menempatkan ratu; klik lagi untuk menghapusnya. Tampilkan serangan memberi titik pada petak yang diserang ratu Anda, dan ratu yang merah saling menyerang. Selesaikan menjalankan pencarian backtracking selangkah demi selangkah dan mempertahankan ratu yang Anda tempatkan. Solusi berikutnya menelusuri setiap solusi secara berurutan, dan Ukuran mengubah papan dari 4×4 hingga 12×12.
Pertanyaan yang sering diajukan
Siapa yang menciptakan teka-teki delapan ratu?
Max Bezzel, komposer soal catur asal Jerman, pada tahun 1848. Franz Nauck menerbitkan kumpulan solusi lengkap yang pertama pada tahun 1850.
Ada berapa solusi?
92 pada papan standar. Jika rotasi dan pencerminan dihitung sebagai satu, ada 12.
Mengapa papan 6×6 punya begitu sedikit solusi?
Papan itu hanya punya 4, semuanya dari satu keluarga. Papan 5×5 yang lebih kecil punya 10. Papan yang lebih besar punya makin banyak: 40 pada 7×7 dan 92 pada 8×8.
Apakah PictorX mengunggah sesuatu?
Tidak. Papan digambar pada kanvas di browser Anda. Simpan mengunduh PNG, dan Sunting membuka gambar itu di editor PictorX.
Related alat
Delapan Ratu
Tempatkan delapan ratu di papan catur sehingga tidak ada ratu yang menyerang ratu lain. Coba sendiri, tonton pencarian backtracking menemukan solusi langkah demi langkah, dan telusuri semua 92 solusi.
Perjalanan Kuda
Lompatkan kuda catur ke setiap petak papan tepat satu kali. Mainkan sendiri dengan petunjuk Warnsdorff, atau tonton Selesaikan menuntaskan perjalanan terbuka atau tertutup. Simpan jalurnya sebagai PNG.
Perjalanan kuda
Sejarah dan matematika perjalanan kuda: Euler dan Warnsdorff, perjalanan terbuka dan tertutup, mengapa papan ganjil tidak punya perjalanan tertutup, dan bagaimana komputer menemukannya.
Menara Hanoi
Pindahkan menara cakram di antara tiga tiang di peramban Anda. Satu cakram setiap kali, tidak pernah yang besar di atas yang kecil. Solusi terpendek adalah 2ⁿ − 1 langkah.
Menara Hanoi
Menara Hanoi: tiga tiang, satu cakram setiap kali, dan tidak pernah yang besar di atas yang kecil. Solusi terpendek adalah 2ⁿ−1 langkah. Édouard Lucas memperkenalkannya pada tahun 1883.
Semut Langton
Jalankan semut Langton di browser. Saksikan simetri, kekacauan, dan jalan raya 104 langkah, lalu coba aturan warna-warni, beberapa semut, kisi heksagon, dan turmite.
Siap ke coba itu?
Buka PictorX di browser Anda — tidak instalasi, tidak credit kartu diperlukan ke mulai.
Coba Delapan Ratu