(Knight’s Tour) One of the more interesting puzzlers for chess buffs is the Knight’s 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? We study this intriguing problem in depth in this exercise. The knight makes L-shaped moves (over two in one direction and then over one in a

perpen- dicular 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 Fig. 6.23.

a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you’ll get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate?
b) Now let’s develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 two-dimensional array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0, as shown in Fig. 6.23, consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two one-dimensional arrays, horizontal and vertical, as follows:

horizontal[ 0 ] = 2 vertical[ 0 ] = -1
horizontal[ 1 ] = 1 vertical[ 1 ] = -2
horizontal[ 2 ] = -1 vertical[ 2 ] = -2
horizontal[ 3 ] = -2 vertical[ 3 ] = -1
horizontal[ 4 ] = -2 vertical[ 4 ] = 1
horizontal[ 5 ] = -1 vertical[ 5 ] = 2
horizontal[ 6 ] = 1 vertical[ 6 ] = 2
horizontal[ 7 ] = 2 vertical[ 7 ] = 1
Let the variables currentRow and currentColumn indicate the row and column of
the knight’s current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements
currentRow += vertical[ moveNumber ];
currentColumn += horizontal[ moveNumber ];
Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard. Run the program. How many moves did the knight make?

c) After attempting to write and run a Knight’s Tour program, you have probably developed some valuable insights. We’ll use these to develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic greatly improves the chance of success. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most troublesome, or inaccessible, squares are the four corners. Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave open those that are easiest to get to, so when the board gets congested near the end of the tour, there will be a greater chance of success.
We may develop an “accessibility heuristic” by classifying each square according to how accessible it is and then always moving the knight to the square (within the knight’s L-shaped moves, of course) that is most inaccessible. We label a two-dimensional array accessibility with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each center square is rated as 8, each corner square is rated as 2 and the other squares have accessibility numbers of 3, 4 or 6
as follows:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
Now write a version of the Knight’s Tour program using the accessibility heuristic.

At any time, the knight should move to the square with the lowest accessibility num-
ber. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour

may begin in any of the four corners. [Note: As the knight moves around the chess-
board, your program should reduce the accessibility numbers as more and more

squares become occupied. In this way, at any given time during the tour, each available
square’s accessibility number will remain equal to precisely the number of squares from
which that square may be reached.] Run this version of your program. Did you get a
full tour? Now modify the program to run 64 tours, one starting from each square of
the chessboard. How many full tours did you get?
d) Write a version of the Knight’s Tour program which, when encountering a tie between two or more squares, decides what square to choose by looking ahead to those squares reachable from the “tied” squares. Your program should move to the square for which the next move would arrive at a square with the lowest accessibility number.

```
// Knight's Tour - access version
// runs one tour
#include
#include
#include
#include
using namespace std;

const int SIZE = 8;

void clearBoard( int [][ SIZE ] );
void printBoard( const int [][ SIZE ] );
bool validMove( int, int, const int [][ SIZE ] );

int main()
{
int board[ SIZE ][ SIZE ];
int currentRow;
int currentColumn;
int moveNumber = 1;
int testRow;
int testColumn;
int horizontal[ SIZE ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ SIZE ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int moveType;
bool done;
bool goodMove;

srand( time( 0 ) );
clearBoard( board ); // initialize array board
currentRow = rand() % 8;
currentColumn = rand() % 8;
board[ currentRow ][ currentColumn ] = moveNumber++;
done = false;

// continue until knight can no longer move
while ( !done )
{
moveType = 0;
testRow = currentRow + vertical[ moveType ];
testColumn = currentColumn + horizontal[ moveType ];
goodMove = validMove( testRow, testColumn, board );

// test if desired move is valid
if ( goodMove )
{
currentRow = testRow;
currentColumn = testColumn;
board[ currentRow ][ currentColumn ] = moveNumber++;
} // end if
else
{
// if move is not legal, try another move
for ( int count = 0; count < SIZE - 1 && !goodMove; count++ )
{
moveType = ++moveType % SIZE;
testRow = currentRow + vertical[ moveType ];
testColumn = currentColumn + horizontal[ moveType ];
goodMove = validMove( testRow, testColumn, board );

// test if new move is valid
if ( goodMove )
{
currentRow = testRow;
currentColumn = testColumn;
board[ currentRow ][ currentColumn ] = moveNumber++;
} // end if
} // end for

// if no valid moves, knight can no longer move
if ( !goodMove )
done = true;
} // end else

// if 64 moves have been made, a full tour is complete
if ( moveNumber - 1 == 64 )
done = true;
} // end while

cout << "The tour ended with " << moveNumber - 1 << " moves.\n";

// test and display whether full tour was made
if ( moveNumber - 1 == 64 )
cout << "This was a full tour!\n\n";
else
cout << "This was not a full tour.\n\n";

cout << "The board for this test is:\n\n";
printBoard( board );
} // end main

// function to clear the chess board
void clearBoard( int workBoard[][ SIZE ] )
{
// set all squares to zero
for ( int row = 0; row < SIZE; row++ )
{
for ( int col = 0; col < SIZE; col++ )
workBoard[ row ][ col ] = 0;
} // end for
} // end function clearBoard

// function to print chess board
void printBoard( const int workBoard[][ SIZE ] )
{
// display the headings and squares
cout << " 0 1 2 3 4 5 6 7\n";

for ( int row = 0; row < SIZE; row++ )
{
cout << row;

for ( int col = 0; col < SIZE; col++ )
cout << setw( 3 ) << workBoard[ row ][ col ];

cout << '\n';
} // end for

cout << endl;
} // end function printBoard

// function to determine if move is legal
bool validMove( int row, int column, const int workBoard[][ SIZE ] )
{
// NOTE: This test stops as soon as it becomes false
return ( row >= 0 && row < SIZE && column >= 0 && column < SIZE
&& workBoard[ row ][ column ] == 0 );
} // end function validMove
```
The tour ended with 36 moves.
This was not a full tour.
The board for this test is:
0 1 2 3 4 5 6 7
0 36 17 22 7 20 15 12 5
1 23 8 19 16 11 6 31 14
2 18 35 10 21 32 13 4 0
3 9 24 33 0 27 0 0 30
4 34 0 26 0 0 29 0 3
5 25 0 0 28 0 2 0 0
6 0 0 0 1 0 0 0 0
7 0 0 0 0 0 0 0 0
```
// Knight's Tour - access version
// runs one tour
#include
#include
#include
#include
using namespace std;

const int SIZE = 8;

void clearBoard( int [][ SIZE ] );
void printBoard( const int [][ SIZE ] );
bool validMove( int, int, const int [][ SIZE ] );

int main()
{
int board[ SIZE ][ SIZE ];
int currentRow;
int currentColumn;
int moveNumber = 1;
int access[ SIZE ][ SIZE ] = { 2, 3, 4, 4, 4, 4, 3, 2,
3, 4, 6, 6, 6, 6, 4, 3,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
3, 4, 6, 6, 6, 6, 4, 3,
2, 3, 4, 4, 4, 4, 3, 2 };

int testRow;

int testColumn; int minRow;
int minColumn;
int minAccess = 9;
int accessNumber;
int horizontal[ SIZE ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ SIZE ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
bool done;

srand( time( 0 ) );

clearBoard( board ); // initialize array board
currentRow = rand() % 8;
currentColumn = rand() % 8;
board[ currentRow ][ currentColumn ] = moveNumber++;
done = false;

// continue while knight still has valid moves
while ( !done )
{
accessNumber = minAccess;

// loop through all move types
for ( int moveType = 0; moveType < SIZE; ++moveType )
{
testRow = currentRow + vertical[ moveType ];
testColumn = currentColumn + horizontal[ moveType ];

// make sure move is valid
if ( validMove( testRow, testColumn, board ) )
{
// if move is valid, and has lowest accessNumber
// set square to accessNumber
if ( access[ testRow ][ testColumn ] < accessNumber )
{
accessNumber = access[ testRow ][ testColumn ];
minRow = testRow;
minColumn = testColumn;
} // end inner if

access[ testRow ][ testColumn ]--;
} // end outer if
} // end for

// end if knight has no moves
if ( accessNumber == minAccess )
done = true;
else
{
currentRow = minRow;
currentColumn = minColumn;
board[ currentRow ][ currentColumn ] = moveNumber++;
} // end else
} // end while

cout << "The tour ended with " << moveNumber - 1 << " moves.\n";

// determine and print if a full tour was made
if ( moveNumber - 1 == 64 )
cout << "This was a full tour!\n\n";
else
cout << "This was not a full tour.\n\n";
cout << "The board for this test is:\n\n";
printBoard( board );
} // end main

// function to clear chess board
void clearBoard( int workBoard[][ SIZE ] )
{
// set all squares to zero
for ( int row = 0; row < SIZE; row++ )
{
for ( int col = 0; col < SIZE; col++ )
workBoard[ row ][ col ] = 0;
} // end for
} // end function clearBoard

// function to print chess board
void printBoard( const int workBoard[][ SIZE ] )
{
cout << " 0 1 2 3 4 5 6 7\n";

// print squares
for ( int row = 0; row < SIZE; row++ )
{
cout << row;

for ( int col = 0; col < SIZE; col++ )
cout << setw( 3 ) << workBoard[ row ][ col ];

cout << '\n';
} // end outer for

cout << endl;
} // end function printBoard

// function to determine if move is legal
bool validMove( int row, int column, const int workBoard[][ SIZE ] )
{
// NOTE: This test stops as soon as it becomes false
return ( row >= 0 && row < SIZE && column >= 0 && column < SIZE
&& workBoard[ row ][ column ] == 0 );
} // end function validMove
```
The tour ended with 64 moves.
This was a full tour!
The board for this test is:
0 1 2 3 4 5 6 7
0 8 37 6 47 10 35 30 63
1 5 46 9 36 31 64 11 34
2 38 7 48 45 58 33 62 29
3 43 4 57 32 61 50 55 12
4 22 39 44 49 56 59 28 51
5 3 42 21 60 25 54 13 16
6 20 23 40 1 18 15 52 27
7 41 2 19 24 53 26 17 14