As computers continue increasing in power, we’ll be able to solve more problems with sheer computer power and relatively unsophisticated algorithms. This is the “brute force” approach to problem solving.

a) Use random number generation to enable the knight to walk around the chessboard (in its legitimate L-shaped moves, of course) at random. Your program should run one tour and print the final chessboard. How far did the knight get?
b) Most likely, the preceding program produced a relatively short tour. Now modify your program to attempt 1000 tours. Use a one-dimensional array to keep track of the number of tours of each length. When your program finishes attempting the 1000 tours, it should print this information in neat tabular format. What was the best result?
c) Most likely, the preceding program gave you some “respectable” tours, but no full tours. Now “pull all the stops out” and simply let your program run until it produces a full tour. [Caution: This version of the program could run for hours on a powerful computer.] Once again, keep a table of the number of tours of each length, and print this table when the first full tour is found. How many tours did your program attempt before producing a full tour? How much time did it take?
d) Compare the brute force version of the Knight’s Tour with the accessibility heuristic version. Which required a more careful study of the problem? Which algorithm was more difficult to develop? Which required more computer power? Could we be certain (in advance) of obtaining a full tour with the accessibility heuristic approach? Could we be certain (in advance) of obtaining a full tour with the brute force approach? Argue the pros and cons of brute force problem solving in general.

```
#include
#include
#include
#include
using namespace std;

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

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

srand( time( 0 ) );

currentRow = rand() % SIZE;
currentColumn = rand() % SIZE;
board[ currentRow ][ currentColumn ] = moveNumber++;
done = false;

// continue until knight can no longer move
while ( !done )
{
moveType = rand() % SIZE;
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 random 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 good
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 has ended with " << moveNumber - 1 << " moves.\n";

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

// function to test whether a square is on the board
// and has not been visited yet
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

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

// print the rows and columns of the chess board
for ( int row = 0; row < SIZE; row++ )
{
cout << row;

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

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

cout << endl;
} // end function printBoard
```
The tour has ended with 26 moves.
This was not a full tour.
The board for this random test was:
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 20 0
1 0 0 23 0 21 0 17 0
2 24 0 0 0 16 0 0 19
3 0 0 0 22 0 18 15 0
4 0 25 0 0 0 13 0 11
5 1 6 3 0 0 10 0 14
6 26 0 8 0 4 0 12 0
7 7 2 5 0 9 0 0 0
```
#include
#include
#include
#include
using namespace std;

const int SIZE = 8;
const int TOURS = 1000;
const int MAXMOVES = 65;

bool validMove( int, int, int, const int [][ SIZE ] );

int main()
{
int currentRow;
int currentColumn;
int moveType;
int moveNumber;
int testRow;
int testColumn;
int moveTotal[ MAXMOVES ] = {};
int goodMove;
int board[ SIZE ][ SIZE ];
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 ) );

// set all squares equal to 0
for ( int i = 0; i < TOURS; ++i )
{
for ( int row = 0; row < SIZE; row++ )
{
for ( int col = 0; col < SIZE; col++ )
board[ row ][ col ] = 0;
} // end for
moveNumber = 1;

currentRow = rand() % SIZE;
currentColumn = rand() % SIZE;
board[ currentRow ][ currentColumn ] = moveNumber++;
done = false;

// continue while knight still has valid moves
while ( !done )
{
moveType = rand() % SIZE;
testRow = currentRow + vertical[ moveType ];
testColumn = currentColumn + horizontal[ moveType ];
goodMove = validMove( testRow, testColumn, moveType, board );

// if desired move is valid, move knight to square
if ( goodMove )
{
currentRow = testRow;
currentColumn = testColumn;
board[ currentRow ][ currentColumn ] = moveNumber++;
} // end if
else
{
// if move is invalid, test other possible moves
for ( int count = 0; count < SIZE - 1 && !goodMove; count++ )
{
moveType = ++moveType % SIZE;
testRow = currentRow + vertical[ moveType ];
testColumn = currentColumn + horizontal[ moveType ];
goodMove = validMove(
testRow, testColumn, moveType, board );

// if move is valid, move knight to square
if ( goodMove )
{
currentRow = testRow;
currentColumn = testColumn;
board[ currentRow ][ currentColumn ] = moveNumber++;
} // end if
} // end for

// if no valid moves, while loop exits
if ( !goodMove )
done = true;
} // end else

// if full tour is made, while loop exits
if ( moveNumber - 1 == 64 )
done = true;
} // end while

moveTotal[ moveNumber ]++;
} // end outer for
// display how many tours of each move number were made
for ( int j = 1; j < MAXMOVES; j++ )
{
if ( moveTotal[ j ] )
cout << "There were " << moveTotal[ j ] << " tours of " << j
<< " moves." << endl;
} // end for
} // end main

// function to determine if a move is legal
bool validMove(
int testRow, int testColumn, int moveType, const int board[][ SIZE ] )
{
// test if square is on board and if knight has previously visited it
if ( testRow >= 0 && testRow < SIZE && testColumn >= 0 &&
testColumn < SIZE )
return board[ testRow ][ testColumn ] != 0 ? false : true;
else
return false;
} // end function validMove
```
There were 1 tours of 5 moves.
There were 1 tours of 6 moves.
There were 3 tours of 7 moves.
There were 1 tours of 8 moves.
There were 2 tours of 9 moves.
There were 1 tours of 10 moves.
There were 3 tours of 11 moves.
There were 1 tours of 12 moves.
There were 5 tours of 13 moves.
There were 2 tours of 14 moves.
There were 6 tours of 15 moves.
There were 4 tours of 16 moves.
There were 6 tours of 17 moves.
There were 6 tours of 18 moves.
There were 10 tours of 19 moves.
There were 6 tours of 20 moves.
There were 11 tours of 21 moves.
There were 8 tours of 22 moves.
There were 17 tours of 23 moves.
There were 10 tours of 24 moves.
There were 14 tours of 25 moves.
There were 11 tours of 26 moves.
There were 27 tours of 27 moves.
There were 20 tours of 28 moves.
There were 23 tours of 29 moves.
There were 20 tours of 30 moves.
There were 24 tours of 31 moves.
There were 38 tours of 32 moves.
There were 33 tours of 33 moves.
There were 22 tours of 34 moves.
There were 28 tours of 35 moves.
There were 25 tours of 36 moves.
There were 41 tours of 37 moves.
There were 31 tours of 38 moves.
There were 38 tours of 39 moves.
There were 37 tours of 40 moves.
There were 38 tours of 41 moves.
There were 31 tours of 42 moves.
There were 43 tours of 43 moves.
There were 30 tours of 44 moves.
There were 35 tours of 45 moves.
There were 24 tours of 46 moves.
There were 31 tours of 47 moves.
There were 32 tours of 48 moves.
There were 37 tours of 49 moves.
There were 16 tours of 50 moves.
There were 26 tours of 51 moves.
There were 25 tours of 52 moves.
There were 29 tours of 53 moves.
There were 14 tours of 54 moves.
There were 17 tours of 55 moves.
There were 14 tours of 56 moves.
There were 4 tours of 57 moves.
There were 10 tours of 58 moves.
There were 3 tours of 59 moves.
There were 1 tours of 60 moves.
There were 4 tours of 61 moves.