// Exercise 4.24 Part C Solution
// Knight's Tour - access version
// runs one tour
/*
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 number. 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 chessboard,
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?
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int SIZE = 8;
void clearBoard(int[][SIZE]);
void printBoard(const int[][SIZE]);
void printAccess(const int[][SIZE]);
bool validMove(int, int, const int[][SIZE]);
int main()
{
int board[SIZE][SIZE], currentRow, currentColumn, moveNumber = 0,
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 },
testRow, testColumn, minRow, minColumn,
minAccess = 9, accessNumber,
horizontal[SIZE] = { 2, 1, -1, -2, -2, -1, 1, 2 },
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;
while (!done) {
accessNumber = minAccess;
for (int moveType = 0; moveType < SIZE; ++moveType) {
testRow = currentRow + vertical[moveType];
testColumn = currentColumn + horizontal[moveType];
if (validMove(testRow, testColumn, board)) {
if (access[testRow][testColumn] < accessNumber) {
accessNumber = access[testRow][testColumn];
minRow = testRow;
minColumn = testColumn;
}
--access[testRow][testColumn];
}
}
if (accessNumber == minAccess)
{
done = true;
printf("minAccess = %d",minAccess);
printf("\n\n");
printf("\n*********************************\n");
printAccess(access);
printf("\n*********************************\n");
}
else {
currentRow = minRow;
currentColumn = minColumn;
board[currentRow][currentColumn] = ++moveNumber;
printf("\n\n");
printBoard(board);
printf("\n\n");
printAccess(access);
}
}
cout << "The tour ended with " << moveNumber << " moves.\n";
if (moveNumber == 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);
printf("\n\n");
printAccess(access);
cin.get();
return 0;
}
void clearBoard(int workBoard[][SIZE])
{
for (int row = 0; row < SIZE; ++row)
for (int col = 0; col < SIZE; ++col)
workBoard[row][col] = 0;
}
void printBoard(const int workBoard[][SIZE])
{
//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';
}
cout << endl;
}
void printAccess(const int workAccess[][SIZE])
{
//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) << workAccess[row][col];
cout << '\n';
}
cout << endl;
}
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);
}
