Aturan Warnsdorff dan Algoritma Backtracking pada Permainan The Knight’s Tour

Wida Nurul Fauziyah, Yurika Permanasari, Respitawulan Respitawulan

Abstract


Abstract. The Knight's Tour game is a game played by one person involving a knight's on the chessboard. The rules of the game are simple, the player only needs to move the knight’s so that the knight’s occupies all of the plots on the chessboard exactly once with the same stride as in the chess game which is L-shaped, which longwise two plots and widens one plot. The Knight’s Tour problem can be solved by the Warnsdorff rules and backtracking algorithm. The Warnsdorff Rules are steps that seek the completion of The Knight's Tour by selecting the next step choice of the fewest plots, isolated plots tend to be visited first, while the backtracking algorithm is a structured and systematic method of finding solutions by taking decisions one by one until a valid solution is found.

Keywords: The Knight’s Tour, Warnsdorff Rule, Backtracking Algorithm

Abstrak. The Knight’s Tour merupakan permainan yang dimainkan oleh satu orang yang melibatkan kuda (knight’s) pada papan catur. Peraturan dari permainan ini sederhana, pemain hanya perlu memindahkan kuda sehingga kuda tersebut tepat menempati semua petak pada papan catur tepat satu kali dengan langkah gerak kuda sama seperti pada permainan catur yaitu berbentuk L, yaitu memanjang dua petak dan melebar satu petak. Permasalahan The Knight’s Tour dapat diselesaikan dengan aturan Warnsdorff dan algoritma backtracking.  Aturan Warnsdorff merupakan sebuah langkah-langkah yang mencari penyelesaian The Knight’s Tour dengan cara memilih pilihan langkah berikutnya dari sebuah petak yang jumlahnya paling sedikit, petak yang terisolasi cenderung untuk dikunjungi terlebih dahulu, sedangkan algoritma backtracking merupakan metode terstruktur dan sistematis dalam pencarian solusi dengan cara mengambil keputusan satu per satu hingga ditemukan solusi yang valid.

Kata Kunci: The Knight’s Tour, Aturan Warnsdorff, Algoritma Backtracking


Keywords


The Knight’s Tour, Aturan Warnsdorff, Algoritma Backtracking

Full Text:

PDF

References


Susi Meliani, Yurika Permanasari, Icih Sukarsih, “Pewarnaan Titik pada Graf Menggunakan Algoritma Baris dan Implementasinya dalam Matlab,” dalam Spesia Universitas Islam Bandung, Bandung, 2016.

L. S dan W. C, “Optimal Algorithms for Constructing Knight's Tours on Arbitary nxm Chessboards,” 2005, pp. 219-232.

Fari Ardilla Ardianto, Yurika Permanasari, Icih Sukarsih, “Penerapan Pewarnaan Graf sebagai Metode untuk Mencari Solusi Permainan Sudoku,” dalam Spesia Universitas Islam Bandung, Bandung, 2015.

Y. U. Micky, “Penerapan Teori Graf untuk Menyelesaikan Teka-Teki Permainan The Knight's Tour,” 2015.

P. Cull dan J. Curtins, “Knight's Tour Revisited,” June 1978.

C. A, H. T, M. H dan W. I, “Solution of The Knight's Hamiltonian Path Problem on Chessboards,” 1994, pp. 125-134.

Yusuf Ibrahim Abdallah, Yani Ramdani, Yurika Permanasari, “Application of Graph Hamilton on Determining the Shortest Route of Trans Metro Bandung,” Proceedings of the International Conference on Industrial Engineering and Operations Management, pp. 1579-1580, 2019.

R. Ahmad Genadi, “Algoritma Penyelesaian Knight's Tour Problem,” 2017.




Flag Counter