Knights Tour

One of the more interesting puzzles for chess buffs is the Knights Tour problem. The question is this: Can the chess piece called the knight move around an empty chess-board and touch each of the 64 squares once and only once?

The knight makes L-shaped moves (over two in one direction then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in Figure 1. See image.

Write a program that will move the knight around a chessboard. The board is represented by an 8-by-8 two dimensional array board. Your program must use the array template class. Your program must describe each of the possible moves in terms of both their horizontal and vertical components. For example, as seen above, move #0 requires two horizontal moves to the right and one vertical move up. Move #7 requires two horizontal moves to the right and one vertical move down. Move #5 requires two vertical moves down and one horizontal move left, and so on. All possible eight moves can be captured using two one-dimensional arrays as seen below, where negative numbers represent left moves for horizontal moves and upward moves for vertical moves.

Table 1 Eight Possible Moves Identified by Move Numbers 0 7. See image.

Your program should choose the initial location of the knight to a random position (row and column) within the board. From this position, the knight should attempt to move to a valid non-visited location. On each move, you are required to keep track of the move number, as seen in Figure 2 below. As seen in Figure 2, the first move is made to position with row=5 and column=2; the second move is made to position with row=4 and column=4; the third move is made to position with row=3 and column=6, and so on. For the particular instance of the program in Figure 2, the maximum number of moves was 54; therefore, a full tour of 64 moves was not possible. Your program is required to keep track of this information and produce an output similar to Figure 2. Your program should execute until a full-tour is achieved (which is unlikely) or until the knight can no longer move. The required output of the program includes:

• The number of moves in the tour
• Status message indicating whether a full tour was achieved or not.
• The final state of the board with move numbers identified (as seen below).

Notice that since we are using random numbers to simulate the initial position of the knight, your output should never be the same. See image.