BacktrackingLanjutFase E–FE1E5

Knight's Tour

Knight's Tour mencari jalur di mana seekor kuda catur mengunjungi setiap kotak papan tepat satu kali. Algoritma memakai backtracking dengan heuristik Warnsdorff: langkah legal diurutkan berdasarkan jumlah lanjutan tersedia sehingga kotak paling terkurung dikunjungi lebih dulu, lalu mundur bila menemui jalan buntu. Visualisasi menomori kotak sesuai urutan kunjungan sampai seluruh 25 kotak terlewati.

Contoh kasus

Merancang rute inspeksi mesin di lantai pabrik agar satu petugas melewati semua titik pemeriksaan tepat sekali tanpa mengulang.

Silabus

Knight's Tour mencari jalur agar kuda catur mengunjungi setiap kotak tepat sekali, memakai backtracking sambil mundur dari jalan buntu.

Tujuan Belajar

·Memahami pola langkah L kuda catur pada papan
·Menjelaskan cara backtracking membatalkan langkah yang gagal
·Menerapkan heuristik Warnsdorff untuk mempercepat pencarian

Cara Kerja

·Kuda mencoba semua langkah L yang legal dari posisi sekarang
·Tambahkan kotak baru ke jalur bila masih kosong, lalu melangkah rekursif
·Heuristik Warnsdorff mendahulukan kotak dengan paling sedikit lanjutan
·Bila menemui jalan buntu, batalkan langkah terakhir (pop) dan coba opsi lain
·Berhenti saat seluruh kotak papan berhasil dikunjungi tepat sekali

Prasyarat

·Backtracking
·Grid 2D

Contoh Nyata

·Merancang rute inspeksi mesin agar tiap titik dicek tepat sekali
·Perencanaan rute petugas yang harus singgahi semua lokasi tanpa mengulang
·Menyelesaikan teka-teki papan pada game strategi

Kompleksitas Eksponensial tanpa heuristik; hampir linear dengan Warnsdorff