0

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