Knight's Tour + heuristics

[sarmar610]

From Wikipedia for the uninformed: "A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once."

I've come up with this code, but the knight goes off the 8x8 board after 6 moves, completes 6 more moves, and comes back on the board for the final 6 moves. I am not sure what is going on, but I believe it is an issue with my logic?

Also, commented out at the bottom of my code I've included a heuristic (each number in the array represents the amount of spaces from which that space can be moved to) and a function to find the smallest integer in the array. Could anyone provide any tips on how to implement this heuristic into my program?

const int rows = 8,
		  columns = 8;

//Current row and column the knight is on
int currentRow = 0,
	currentColumn = 0;

//Sets up the 8 move types the knight can make
int horizontal[8] = { 2, 1, -1, -2, -2, -1, 1, 2 },
	vertical[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };

//Sets up 8x8 chessboard and initializes to 0
int board[rows][columns] = { 0 };

//Function prototypes
void printBoard(int[][columns]);
bool onBoard(int, int);
bool notVisited(int[][8]);

int main()
{
	//Sets the counter at 1
	int counter = 1;

	//Knight's previous row and column
	int pastRow,
		pastColumn;

	//Starts the move number at move type 0
	int moveNumber = 0;

	//For loop to move the Knight around the board while the counter is below 65
	for (int i = 1; i < 65; i++)
	{
		pastRow = currentRow;
		pastColumn = currentColumn;

		//Moves the Knight horizontally and vertically to create an L-shaped move
		currentRow += horizontal[moveNumber];
		currentColumn += vertical[moveNumber];

		//Calls functions to determine if the knight is on the board and that the proposed square has not been visited
		if (onBoard(currentRow, currentColumn) && notVisited(board))
		{
			board[currentRow][currentColumn] = counter;
			counter++;
			moveNumber = 1;
		}
		else
		{
			//Sets the Knight back to its previous position, as the proposed position is invalid
			currentRow = pastRow;
			currentColumn = pastColumn;
			//Increments moveNumber to try the next move
			moveNumber++;
		}
	}

	//Displays board
	cout << counter << "\n";
	cout << endl;
	printBoard(board);

	cin.get();
	cin.get();
	return 0;
}

//Function to display the board after the Knight cannot move anymore
void printBoard(int board[rows][columns])
{
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < columns; j++)
			cout << board[i][j] << ' ';

		cout << endl;
	}
}

//Function to check if knight's proposed move is on the board
bool onBoard(int currentRow, int currentColumn)
{
	if ((currentRow > 0) && (currentRow < 7) &&
		(currentColumn > 0) && (currentColumn < 7))
	{
		return true;
	}
	else
	{
		return false;
	}
}

//Function to check if the knight's proposed move is to a square that has not been visited
bool notVisited(int board[][8])
{
	if ((board[currentRow][currentColumn] == 0))
	{
		return true;
	}
	else
	{
		return false;
	}
}

/*
int accessibility[8][8] = { { 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 searchArray(int target, int arraySize, int array[])
{
	int foundIndex = -1;
	for (int i = 0; i < arraySize; i++)
	{
		if (array[i] == target)
		{
			foundIndex = i;
			break;
		}
	}
}
*/

[cire]

I've come up with this code, but the knight goes off the 8x8 board after 6 moves, completes 6 more moves, and comes back on the board for the final 6 moves. I am not sure what is going on, but I believe it is an issue with my logic?

You make moves, then check to see if the move was valid. Of course, the knight is going to go off the board (although, I doubt if your description of what is happening is accurate.)

Array indexes start at 0, so line 47 should be setting moveNumber to 0. You make no effort to ensure that moveNumber remains a valid index (doesn't run off the end of the arrays.)

Also, commented out at the bottom of my code I've included a heuristic (each number in the array represents the amount of spaces from which that space can be moved to) and a function to find the smallest integer in the array. Could anyone provide any tips on how to implement this heuristic into my program?

A more pressing concern might be "How do you undo moves that render a knight's tour impossible?"

[sarmar610]

You are correct, my description was not at all accurate! Maybe I need to get my eyes checked. Thank you for the help.