Knights Tour problem

[David321]

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;
}

[David321]

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

[David321]

Someone has to know!

[TrustyTony]

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

[David321]

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

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

[sfuo]

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").

[David321]

You're right, I didn't learn about structures yet. When I learn about them, I'll be sure to come back and go over your code, so I can understand what you did.
Also, if anyone is interested in the correct version of this code, Sane on programmingforums.org helped me out. Here's the link http://www.programmingforums.org/post217625.html

[raptr_dflo]

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;
}