Tentang Perjalanan Kuda | Aturan Warnsdorff, perjalanan terbuka dan tertutup

Teka-teki kuno

Dalam Kavyalankara, karya penyair India Rudrata pada abad ke-9, sebuah bait disusun di atas setengah papan catur sehingga bisa dibaca mengikuti jalur kuda. Leonhard Euler menulis kajian matematis pertama tentang perjalanan kuda pada tahun 1759, lengkap dengan cara membangun perjalanan dan mengubahnya menjadi perjalanan tertutup.

Lintasan dalam graf

Bayangkan setiap petak sebagai titik dan setiap langkah kuda sebagai garis di antara dua titik. Perjalanan kuda lalu menjadi lintasan yang mengunjungi setiap titik tepat satu kali, yang oleh matematikawan disebut lintasan Hamilton; perjalanan tertutup adalah siklus Hamilton. Pada kebanyakan jaringan, lintasan seperti itu sangat sulit ditemukan. Jaringan kuda murah hati: perjalanannya begitu banyak sehingga aturan yang baik cepat menemukan salah satunya.

Aturan Warnsdorff

H. C. von Warnsdorff menjelaskan aturannya pada tahun 1823: selalu lompat ke petak yang menyisakan langkah lanjutan paling sedikit. Petak di sepanjang tepi punya sedikit tetangga, jadi aturan ini mengunjunginya lebih awal alih-alih membiarkannya terisolasi. Jika dua petak sama nilainya, harus ada pilihan, dan pilihan yang sial tetap bisa membuat kuda buntu. Di aplikasi, angka emas menandai petak yang akan dipilih aturan ini.

Mencari dengan runut balik

Selesaikan mengikuti urutan Warnsdorff, tetapi tidak memercayainya begitu saja. Ia menelusuri sedalam mungkin lebih dulu, dan begitu sebuah petak yang belum dikunjungi tidak bisa dicapai lagi, ia meninggalkan cabang itu dan mencoba langkah berikutnya. Pada papan hingga 10×10, ia biasanya langsung menemukan perjalanan. Jika jalur Anda sendiri sudah mengurung kuda, ia mundur beberapa langkah lebih dulu.

Warna dan perjalanan tertutup

Setiap langkah kuda mengganti warna petak. Pada papan ganjil seperti 5×5, petak yang berwarna sama dengan petak sudut lebih banyak satu daripada warna lainnya, sehingga perjalanan harus dimulai dan berakhir di warna petak sudut. Perjalanan tertutup mustahil di sana, karena putaran yang warnanya berselang-seling memiliki jumlah petak yang sama untuk setiap warna. Pada papan genap, perjalanan tertutup ada mulai 6×6.

Coba di PictorX

Buka Perjalanan Kuda dan klik sebuah petak untuk memulai. Petak yang disorot adalah lompatan yang sah, angka emas adalah pilihan Warnsdorff, dan papan mencatat urutan langkah Anda. Ukuran mengatur papan dari 5×5 hingga 10×10, Perjalanan tertutup meminta Selesaikan mencari putaran, dan Urungkan menarik kembali langkah mana pun. Simpan jalur yang sudah jadi sebagai PNG.

Pertanyaan yang sering diajukan

Siapa yang pertama kali mempelajari perjalanan kuda?

Perjalanan kuda sudah dikenal jauh sebelum ada yang mempelajarinya secara matematis. Leonhard Euler menulis kajian matematis pertama pada tahun 1759, dan Warnsdorff memberikan aturannya pada tahun 1823.

Apakah ada perjalanan pada setiap papan?

Papan persegi mulai 5×5 punya perjalanan terbuka, dan papan genap mulai 6×6 juga punya perjalanan tertutup. Papan 2×2, 3×3, dan 4×4 sama sekali tidak punya perjalanan.

Berapa banyak perjalanan pada papan catur?

Ada 26.534.728.821.064 perjalanan tertutup jika sebuah perjalanan dan perjalanan yang sama dalam arah sebaliknya dihitung terpisah. Jumlah perjalanan terbuka sekitar 19,6 kuadriliun.

Apakah PictorX mengunggah sesuatu?

Tidak. Papan digambar pada kanvas di browser Anda. Simpan mengunduh PNG, dan Sunting membuka gambar itu di editor PictorX.