Analisis dan optimalisasi algoritme Warnsdorff pada permainan puzzle catur Knight's Tour

Abstract

Knight’s Tour is a puzzle game that requires a Knight in a Chess game to visit all of squares on an empty Chess board where each squares can only be visited once. It can be solved with some methods. One of the method is Warnsdorff Algorithm. Warnsdorff Algorithm can find Knight’s Tour solution in linear time, but it couldn’t always find the solution so its effectivity is not always 100%. The objective of the research is to investigate how effective the Warnsdorff Algorithm is to find a Knight’s Tour. There are some methods to improve the effectivity of Warnsdorff Algorithm. One of them is Roth Method by Arnd Roth. He proposed that the knight take a step that is nearest to the side of the board whenever it meets a tie condition. There is also a method by Vahaaho. He proposed that the knight take a step that is farthest from its first step whenever it meets a tie condition. Those two methods can also be combines so the knight will take a step that is nearest to the side of the board and also farthest from its first step. Then those methods will be tested to know how good they improve the effectivity of the original Warnsdorff Algorithm. After testing the algorithm on variety size of board, that is 6x6 to 20x20, the original Warnsdorff Algorithm has a pretty high effectivity score, but most of it is just around 90% to 95%. But with those three optimalisation, the effectivity of the algorithm can be improved to about 98% to 100%.