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