Ryan Avery

Knights Tour


The Knight's Tour problem can be described as follows: A knight is placed on a chess board of size n-by-n squares where n > 2. If possible, move the knight in such a way that it lands on each square of the board exactly one time. This is the problem that was given to me in this assignment for my CS-421, Design and Analysis of Algorithms class in the summer of 2016.

In this program the user inputs four parameters: the heuristic to use during the algorithm, the size of the board, and the x and y coordinates of the staringlarge project picture location of the knight. Once these parameters are provided, the program will find a solution and print it to the console by writing the board to the screen and showing the steps (which start at 1 and end at n-squared) that the knight can take in order to make its complete tour.

The first parameter which selects the heuristic to use can have a value of either 0, 1, or 2. A value of 0 means that no heuristic will be used, and the search for possible moves will start at the top left and move in a clockwise direction ending in the bottom left. If a value of 1 is given, the algorithm will start its search from its current square by first expanding those unused squares which are closest to the edge of the board. If a value of 2 is given, the algorithm will use Warnsdorf's rule as its heuristic. This means that when searching for a square to move to, the algorithm will first expand the square which, if the knight were to move to, the knight would have the fewest possible valid moves to make from that location.

After having completed this assignment I ran a test of the different heuristics on a board size of 7 and having the knight start on the 1-1 location. Using no heuristic took the algorithm 254,727,173 moves to complete. Using the first heuristic (the edge-preferring heuristic) took the algorithm 2,798 moves to complete. Using the Warnsdorf's rule heuristic, however, took the algorithm only 127 moves to find a valid solution.