I've been having some trouble making the knights tour (getting a knight to go around a chessboard without touching the same square twice) work correctly. Right now the max amount of moves I can get out of it is 59. I can't figure out any reason why it shouldn't go to 64 moves (which means it's completed). I just learned about multidimensional arrays, so if you're solution is even slightly advanced it probably won't help me. Please help me! Here's my code:

#include <iostream>

using std::cout;
using std::endl;
using std::cin;

const int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
const int vertical[8]={-1,-2,-2,-1,1,2,2,1};

int moveKnight(int board[][8]);
bool check( int board[][8]);
bool anyValid(int board[][8],int row, int column);
void printArray(int [], int size);
void resetArrayOneD(int [], int);
void resetArrayTwoD(int [][8],int);

int main()
{
	int board[8][8];
	int status=0;
	
	resetArrayTwoD(board,8);
	status=moveKnight(board);
	
	system("pause");
	return 0;
}

int moveKnight(int board[][8])
{
	int currentRow=0;
	int currentColumn=0;
	int moves[64];
	int counter=0;

	for (int i=0;i<64;i++)
		moves[i]=-1;

	for (int i=0; i<=7;i++)
		for (int j=0;j<=7;j++)
		{
			//reset starting point and board
			resetArrayTwoD(board,8);
			resetArrayOneD(moves,64);
			counter=0;

			currentRow=i;
			currentColumn=j;
			
			board[i][j]=1;
			
			for (int k=0;k<=7;k++) //cycle through the moves possible
				if (currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 &&  board[currentRow+vertical[k]][currentColumn+horizontal[k]]==0 )
				{
					//if it's not off the board and the spot wasn't taken
					currentRow+=vertical[k];
					currentColumn+=horizontal[k];
					board[currentRow][currentColumn]=1;
					moves[counter]=k;
					counter++;
					//reset moves to -1, the for will increment it to 0
					k=-1;
				}
				else if ((currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 && anyValid(board,currentRow, currentColumn)==0)||k==7)
				{
					//if it's not off the board but there are no valid moves;  we need to backtrack
					//we are taking away the PREVIOUS move
					do
					{
					counter--;
					board[currentRow][currentColumn]=0;
					currentRow-=vertical[moves[counter]];
					currentColumn-=horizontal[moves[counter]];
					//have to reset some moves
					k=moves[counter]+1;
					//get rid of the last move recorded
					moves[counter]=-1;
					}while (k>7);
				}
				else if (counter==63)// && check(board))
				{
					//did it
					cout<<"Start at row "<<i<<" column "<<j<<endl;
					printArray(moves, 64);
					return 1;
				}
		}

}

void printArray(int a[], int size)
{
	for (int i=0; i<size;i++)
		cout<<a[i]<<endl;
}

//see if it completed the tour
bool check (int board[][8])
{
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			if (board[i][j]==0)
				return 0;
				
	return 1;
}

//check if there are any valid moves to be made by cycling through the moves array
//0 means no moves left
bool anyValid(int board[][8],int row, int column)
{
	for (int i=0;i<7;i++)
	{
		if (row+vertical[i]<8 && row+vertical[i]>=0 && column+horizontal[i]<8 && column+horizontal[i]>=0 && board[row+vertical[i]][column+horizontal[i]]==0)
			return 1;
	}

	return 0;
}

void resetArrayOneD(int a[], int size) //resets to -1
{
	for (int i=0;i<size-1;i++)
	{
		a[i]=-1;
	}
}

void resetArrayTwoD(int a[][8], int size)
{
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			a[i][j]=0;
}

I'm getting the feeling that something is supposed to happen when the counter goes to 0...

Writer of the code should know what he is planning to do.

Is that you're signature or something? Not very helpful:confused:

I think your method in general is the problem. I looked up Knight's Tour in Wikipedia and read the Wansdorff section and came up with my own code. This method is really easy to implement because I had never heard of this Knights Tour puzzle and I put this together in a few hours.

The only thing that might be slightly advanced and you have not seen is a structure and its operators but the whole point they were put in was because it is easier to think in objects (a position has an x and y value and then the operators just allow you to add them together).

Here is what I came up with and it is loosely based off yours.

#include <iostream>
#include <ctime>
#include <cstdlib> //used for CLS and PAUSE
#include <cstring>

using namespace std;

//board size
#define XDIM 8
#define YDIM 8

struct position
{
	int _x, _y; //data
	position(int x = 0, int y = 0) //constructor (default values of 0, 0)
	{
		_x = x;
		_y = y;
	}
	position operator +(position rhs) //allows the use of the + operator with position structures
	{
		return position(_x+rhs._x, _y+rhs._y);
	}
	void operator += (position rhs) //allows the use of the += operator with position structures
	{
		_x += rhs._x;
		_y += rhs._y;
	}
};

bool Move(bool[][YDIM], position&);
void PrintBoard(bool[][YDIM], position);
int GetNextMove(bool[][YDIM], position);
int GetNumMoves(bool[][YDIM], position, bool = false);
int GetFewestMoves(int[8]);

position moves[] = {position(-2, 1), position(-1, 2), position(1, 2), position(2, 1), position(-2, -1), position(-1, -2), position(1, -2), position(2, -1)};

int main()
{
	bool board[XDIM][YDIM];
	memset(board, 1, XDIM*YDIM);

	srand(time(NULL));
	position pos(rand()%8, rand()%8); //sets random starting position

	PrintBoard(board, pos); //prints empty board

	time_t previousTime = clock();
	while( Move(board, pos) )
	{
		//remove contents of the while loop to disable prints at time steps
		while( previousTime + 250 > clock() ){};
		PrintBoard(board, pos);
		previousTime = clock();
	}
	PrintBoard(board, pos); //prints completed solution

	system("PAUSE");
    return 0;
}


bool Move( bool board[][YDIM], position &pos )
{
	board[pos._x][pos._y] = false;

	int nextMoveIndex = GetNextMove(board, pos);

	if( nextMoveIndex == -1 )
		return false;

	pos += moves[nextMoveIndex];

	return true;
}

void PrintBoard(bool board[][YDIM], position pos)
{
	system("CLS");
	for( int r = 0; r < YDIM; r++ )
	{
		for( int c = 0; c < XDIM; c++ )
		{
			if( r == pos._y && c == pos._x ) //this just shows where the current position is
				cout << char(1);
			else if( board[c][r] )
				cout << "o";
			else
				cout << "x";
		}
		cout << endl;
	}
	cout << endl << endl;
}

int GetNextMove(bool board[][YDIM], position pos)
{
	int numMoves[8];
	for( int i = 0; i < 8; i++ )
		numMoves[i] = GetNumMoves(board, pos+moves[i]);

	int nextMoveIndex = GetFewestMoves(numMoves);

	if( nextMoveIndex != -1 )
		return nextMoveIndex;

	//this is to check if there is one more move left
	if( GetNumMoves(board, pos, true) == 0 )
		return -1;

	for( int i = 0; i < 8; i++ )
	{
		position curPos = pos+moves[i];
		if( (curPos._x < XDIM && curPos._x >= 0 && curPos._y < YDIM && curPos._y >= 0) && board[curPos._x][curPos._y] == true )
			return i;
	}

	return -1;
}

//returns the number of moves possible from the position passed in
int GetNumMoves( bool board[][YDIM], position in, bool finalMoveCheck )
{
	int counter = 0;

	if( finalMoveCheck == false ) //if this wasn't here then it would not move to the last square
		if( (in._x >= XDIM || in._x < 0) || (in._y >= YDIM || in._y < 0) || board[in._x][in._y] == false )
			return 0;

	for( int i = 0; i < 8; i++ )
	{
		position curPos = in+moves[i];
		if( (curPos._x < XDIM && curPos._x >= 0 && curPos._y < YDIM && curPos._y >= 0) && board[curPos._x][curPos._y] == true )
			counter++;
	}
	return counter;
}

//returns the index of the move that has the least amount of moves to it
int GetFewestMoves(int numMoves[8])
{
	int indexOfFewest = -1;
	for( int i = 0; i < 8; i++ )
	{
		if( indexOfFewest == -1 && numMoves[i] != 0 )
		{
			indexOfFewest = i;
			continue;
		}
		if( indexOfFewest != -1 && numMoves[i] < numMoves[indexOfFewest] && numMoves[i] != 0 )
			indexOfFewest = i;
	}
	return indexOfFewest;
}

Normally I wouldn't use system("CLS") but I saw you were already using system("PAUSE").

For what it's worth, the solutions here are implementations of a DepthFirstSearch algorithm, which maps well onto recursion:

(approximately valid but untested)

int KeepMoving (int [][DIM] board, int start_x, int start_y)
{
    if (NoPossibleMoves(board, start_x, start_y))
        return 0;
    int max_moves = 0;
    for (int k=0; k<=7; k++) {
        int next_x = start_x + horizontal[k];
        int next_y = start_y + vertical[k];
        if (IsValidMove(board, next_x, next_y)) {
            int moves = KeepMoving(board, next_x, next_y);
            if (moves > max_moves)
                max_moves = moves;
        }
    }
    return 1 + max_moves;
}
This article has been dead for over six months. Start a new discussion instead.