Teka-teki 15
Teka-teki 15 adalah baki berisi lima belas ubin bernomor dan satu petak kosong. Geser ubin kembali ke urutannya, dan teka-teki itu selesai. Kelihatannya sederhana, tetapi teka-teki ini memicu demam pada tahun 1880, dan di baliknya ada salah satu bukti paling rapi dalam matematika rekreasi: separuh dari semua posisi tidak akan pernah bisa diselesaikan.
Demam tahun 1880
Teka-teki ini berasal dari Negara Bagian New York pada tahun 1870-an; Noyes Chapman, seorang kepala kantor pos di Canastota, biasanya disebut sebagai penemunya. Pada awal tahun 1880, teka-teki ini menjadi demam, mula-mula di seluruh Amerika Serikat, lalu di Eropa.
14-15 Sam Loyd
Pembuat teka-teki asal Amerika Sam Loyd belakangan mengaku bahwa dialah penemu teka-teki ini, dan mengisahkan hadiah 1.000 dolar bagi siapa saja yang bisa menyelesaikannya dengan hanya 14 dan 15 yang ditukar. Tidak ada yang memenangkan hadiah itu, dan memang tidak ada yang bisa: posisi itu tidak dapat diselesaikan. Klaimnya sebagai penemu pun tidak benar.
Mengapa separuh posisi mustahil
Anggap petak kosong sebagai ubin keenam belas. Setiap geseran menukar petak kosong dengan satu ubin. Untuk kembali ke sudutnya, petak kosong harus bergerak ke kiri sesering ke kanan dan ke atas sesering ke bawah, sehingga posisi dengan petak kosong di sudutnya selalu berjarak sejumlah genap pertukaran dari urutan yang selesai. Menukar 14 dan 15 adalah satu pertukaran, yang ganjil, sehingga tidak ada geseran yang bisa mencapainya. Pada tahun 1879, William Johnson dan William Story membuktikan bahwa tepat separuh dari semua susunan dapat dicapai.
Uji untuk posisi apa pun
Hitung pasangan ubin yang urutannya salah saat Anda membaca baki baris demi baris. Pada papan 3×3 atau 5×5, sebuah posisi dapat diselesaikan jika hitungan itu genap. Pada papan 4×4, tambahkan baris petak kosong yang dihitung dari bawah: posisi dapat diselesaikan jika jumlahnya ganjil.
Penyelesaian dengan komputer
Komputer dapat mencari jalan kembali dengan A*, yang selalu memeriksa posisi paling menjanjikan lebih dulu. Ia memperkirakan langkah yang masih dibutuhkan dari seberapa jauh setiap ubin dari tempat asalnya, ditambah dua langkah untuk setiap pasangan ubin yang saling menghalangi di baris atau kolomnya sendiri. Menemukan solusi terpendek menjadi sangat sulit pada papan besar. Posisi teka-teki 15 tersulit butuh 80 langkah, dan teka-teki 8 tidak pernah butuh lebih dari 31.
Coba di PictorX
Buka Teka-teki 15 dan klik sebuah ubin untuk menggesernya. Acak urutan mencampur ubin menjadi posisi baru yang dapat diselesaikan, Selesaikan memainkan solusi langkah demi langkah, dan Tampilkan ubin yang benar mewarnai angka ubin yang sudah berada di tempatnya. Pilih 14-15 Loyd untuk melihat posisi yang mustahil, dan gunakan Ukuran untuk beralih antara 3×3, 4×4, dan 5×5.
Pertanyaan yang sering diajukan
Siapa yang menciptakan teka-teki 15?
Noyes Chapman, seorang kepala kantor pos di Canastota, New York, biasanya disebut sebagai penemunya, pada tahun 1870-an. Klaim Sam Loyd di kemudian hari atas teka-teki ini tidak benar.
Apakah teka-teki 14-15 dapat diselesaikan?
Tidak. Posisi itu berjarak satu pertukaran dari urutan yang selesai, sedangkan setiap posisi yang dapat dicapai dengan geseran berjarak sejumlah genap pertukaran.
Berapa banyak posisi dalam teka-teki 15?
16 petak itu dapat diisi dengan 20.922.789.888.000 cara. Tepat separuhnya, 10.461.394.944.000, dapat dicapai dengan menggeser.
Apakah PictorX mengunggah sesuatu?
Tidak. Teka-teki digambar pada kanvas di browser Anda. Simpan mengunduh PNG, dan Sunting membuka gambar itu di editor PictorX.
Related alat
Teka-teki 15
Mainkan teka-teki geser 15 klasik di peramban Anda dengan ubin kayu di papan 3×3, 4×4, atau 5×5. Acak urutan, geser satu baris penuh sekaligus, coba 14-15 Sam Loyd yang mustahil, atau tonton Selesaikan menuntaskannya.
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.
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.
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.
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.
Mainkan Teka-teki 15