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

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