# Knight's Tour Recursion Problem

This is a discussion on Knight's Tour Recursion Problem within the C++ Programming forums, part of the General Programming Boards category; Dear members, I'm having a problem with my recusrsion function in my Knight's Tour problem and I 've spent hours ...

1. ## Knight's Tour Recursion Problem

Dear members,

I'm having a problem with my recusrsion function in my Knight's Tour problem and I 've spent hours trying to figure out the solution yet to no avail.

My problem is that when I simply have to step back and take another direction, It will run fine, but when I take one step back and have to take another then it just stops.

Any help would be greatly appreciated, Thanks in advance.

p.s.for example, use beginning postion row 8 column 8. See what happens when you reach move 53 (movecount = 52)
Code:
```#include <iostream>
#include <iomanip>
#include <time.h>

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

const long MaxRows = 8;
const long MaxColumns = 8;

const long HorizontalMoves[] = { 2, 1,-1,-2,-2,-1, 1, 2};
const long VerticalMoves[] =   {-1,-2,-2,-1, 1, 2, 2, 1};

void GetFirstPosition(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[]);
void InitializeBoard(long Board[][MaxColumns]);
void PrintBoard(long Board[][MaxColumns]);
void FindNextMove(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long MoveIndex);
void BackTrack(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long& MoveIndex);
bool OnBoard(long Row, long Column);

int main(void)
{
long CurrentRow = 0;
long CurrentColumn = 0;
long MoveCount = 0;
long Board[MaxRows][MaxColumns] = {0};
long RowMoveHistory[64];
long ColumnMoveHistory[64];
long DirectionHistory[64];
long MoveIndex = 0;

InitializeBoard(Board);
PrintBoard(Board);
GetFirstPosition(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory);
PrintBoard(Board);

do
{
FindNextMove(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory, MoveIndex);

}
while(MoveCount < 65);

cout << "Your knight made it to all 64 squares!" << endl;

return 0;
}

void FindNextMove(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long MoveIndex)
{

bool MoveFound = 0;
while(MoveFound == 0)
{

if(OnBoard((CurrentRow + VerticalMoves[MoveIndex]), (CurrentColumn + HorizontalMoves[MoveIndex])) == 1 && Board[CurrentRow + VerticalMoves[MoveIndex]][CurrentColumn + HorizontalMoves[MoveIndex]] == 0)
{

CurrentRow += VerticalMoves[MoveIndex];
CurrentColumn += HorizontalMoves[MoveIndex];
Board[CurrentRow][CurrentColumn] = MoveCount + 1;

MoveFound = true;

DirectionHistory[MoveCount] = MoveIndex;
RowMoveHistory[MoveCount] = CurrentRow;
ColumnMoveHistory[MoveCount] = CurrentColumn;
MoveCount++;
MoveIndex = 0;

}
else
{
MoveIndex++;

if(MoveIndex == 8)
{

PrintBoard(Board);
system("pause");
BackTrack(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory, MoveIndex);

}

}

}

}

void BackTrack(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long& MoveIndex)
{

MoveCount--;
PrintBoard(Board);
CurrentRow -= VerticalMoves[DirectionHistory[MoveCount]];
CurrentColumn -= HorizontalMoves[DirectionHistory[MoveCount]];
Board[RowMoveHistory[MoveCount]][ColumnMoveHistory[MoveCount]] = 0;

Board[CurrentRow][CurrentColumn] = MoveCount;

MoveIndex = DirectionHistory[MoveCount - 1] + 1;
RowMoveHistory[MoveCount] = 0;
ColumnMoveHistory[MoveCount] = 0;
DirectionHistory[MoveCount - 2] = 0;

if(MoveIndex == 8)
MoveIndex = 0;

system("pause");

}

void InitializeBoard(long Board[][MaxColumns])
{
for (long Row = 0; Row < MaxRows; Row++)
{
for (long Column = 0; Column < MaxColumns; Column++)
{
Board[Row][Column] = 0;
}
}
}

void PrintBoard(long Board[][MaxColumns])
{
system("cls");

cout << "     1  2  3  4  5  6  7  8" << endl;
cout << "   ------------------------" << endl;

for (long Row = 0; Row < MaxRows; Row++)
{
cout << Row + 1 << "| ";

for (long Column = 0; Column < MaxRows; Column++)
{
cout << setw(3) << Board[Row][Column];
}

cout << endl;
}
}

void GetFirstPosition(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[])
{
bool MoveFound = false;
int MoveIndex = 0;
do
{
cout << endl << "Where do you wish to begin?" << endl;
cout << "Row: ";
cin >> CurrentRow;
cout << "Column: ";
cin >> CurrentColumn;
}
while(CurrentRow == 0 || CurrentRow == 0 || CurrentRow > 8 || CurrentColumn > 8);

CurrentRow -= 1;
CurrentColumn -=1;

while(MoveFound == false)
{

if(OnBoard((CurrentRow + VerticalMoves[MoveIndex]), (CurrentColumn + HorizontalMoves[MoveIndex])) == 1 && Board[CurrentRow + VerticalMoves[MoveIndex]][CurrentColumn + HorizontalMoves[MoveIndex]] == 0)
{
Board[CurrentRow][CurrentColumn] = MoveCount + 1;
MoveFound = true;
}
else
{
MoveIndex++;
}
}

RowMoveHistory[MoveCount] = CurrentRow;
ColumnMoveHistory[MoveCount] = CurrentColumn;
DirectionHistory[MoveCount] = MoveIndex;

MoveCount++;
}

bool OnBoard(long Row, long Column)
{

bool Result = false;

if (Row >= 0 && Row < 8 && Column >= 0 && Column < 8)
{
Result = true;
}

return Result;

}```

2. I've only briefly looked at it so maybe somewhere you do take care of this and I missed it, but each square needs it's own move index. Otherwise when you backtrack that new square will use the moveindex of a different square meaning it is possible it won't check all of the possibilities or (and I think this is the error you are getting) it will check the same direction over and over again making it look like it is doing nothing.

Popular pages Recent additions