A knight is a chesspiece which can legally move from a square (i; j) on a chessboard (where i is the row index, and j is the column index) to any of the eight squares (i 1; j 2); (i 1; j + 2); (i + 1; j 2); (i + 1; j + 2); (i 2; j 1); (i 2; j + 1); (i + 2; j 1); (i + 2; j + 1), as long as they are on the chessboard.
You are interested in nding knight’s tours of various n m gameboards. A knight’s tour is a sequence of squares from the gameboard so that each square appears exactly once in the sequence, and each square is a legal knight’s move from its previous square. A tour is closed if there is a legal knight’s move from the last square of the sequence back to the rst square. Otherwise, the tour is open.
You will study a heuristic for this problem. A heuristic (without backtracking) will usually nd a tour, but may occasionally fail to nd a tour. Given a partial tour, you will try to lengthen the tour by adding the next possible square with lowest degree. A square is possible if it is not already in the partial tour, and it is a legal knight’s move from the last square in the partial tour. The degree of a square (i; j) is the number of squares that are reachable using a single knight’s move, and which are not already in the partial tour. Notice that each time you add a new square to the tour, you must decrease the degrees of some squares. To begin the construction, you will pick some square as your initial square, making a partial tour of length one.
Use this heuristic to write a program to nd knight’s tours. The inputs should be n and m, the number of rows and columns on the board, and (i; j), the starting square. (For simplicity, you will only need to do boards where n = m.) The output should be an array such that the rst square contains 1, the last square contains nm, and the kth square contains the number k. If your program fails to nd a tour, it should print out the partial tour it found and a message saying that it failed to nd a full tour.
Test your program by using as starting square each of the 25 squares on a 5 5 gameboard.
Does your program always nd a tour? Are the tours you found open or closed? How many di erent tours does your program nd?
Run your program from 4 di erent initial squares on a 6 6 gameboard. Does your program always nd a tour? Are the tours you found open or closed? How many di erent tours does your program nd?
Run your program from 4 di erent initial squares on a 8 8 gameboard. Does your program always nd a tour? Are the tours you found open or closed? How many di erent tours does your program nd?
