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={2,1,-1,-2,-2,-1,1,2};
const int vertical={-1,-2,-2,-1,1,2,2,1};

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

int main()
{
int board;
int status=0;

resetArrayTwoD(board,8);
status=moveKnight(board);

system("pause");
return 0;
}

int moveKnight(int board[])
{
int currentRow=0;
int currentColumn=0;
int moves;
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[])
{
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[],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[], int size)
{
for (int i=0;i<8;i++)
for (int j=0;j<8;j++)
a[i][j]=0;
}``````

## Recommended Answers

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

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 …

## All 7 Replies

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

Someone has to know!

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

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

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

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

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;
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.