Prosiding SeNTIK STI&K, Vol 3 (2019)

Font Size:  Small  Medium  Large

Implementasi Algoritma Backtracking Pada Knight’s Tourproblem

Akbar Serdano, Muhammad Zarlis Muhammad Zarlis, Dedy Hartama

Abstract


Algoritma Backtracking merupakan algoritma yang berhubungan pada DFS untuk menemukan solusi secara lebih mangkus dari pada algoritma brute force. Algoritma Backtracking secara umum menentukan solusi dengan cara memangkas (pruning) bagian yang tidak mengarah ke solusi. Dalam kehidupan seharihari, algoritma Backtracking sering diterapkan untuk menemukan lokasi yang dituju maupun masalah lainnya. Dalam penelitian ini algoritma Backtracking di implementasikan ke dalam suatu masalah mengenai Knight’s Tour, dimana untuk menemukan solusi yang lebih baik. Knight’s Tour adalah sebuah jalur yang akan di lewati oleh knight pada sebuah papan catur 8 x 8, dimana posisi dimulai dari titik yang ditentukan untuk melewati semua kotak tepat hanya satu kali dilalui pada papan catur 8 x 8. Hasil penelitian ini menunjukkan bahwa algoritma Backtracking dapat menemukan solusi yang lebih optimal dibandingkan algoritma brute force

Full Text: PDF