The Knight’s Tour is a classic chess problem that involves finding a sequence of moves for a knight on a chessboard, such that the knight visits every square exactly once. The knight, a chess piece that moves in an “L”-shape (two squares in one direction and one square perpendicular), must cover the entire chessboard without revisiting any square.
This C++ program is tour of knight on 64 square of chess board. The goal is to place a knight on an empty chess board and then move the knight to each of the remaining 63 squares while only visiting each square once. If on visiting the last square the knight is able to hop to the square on which it first started it is known as a closed tour (and so the knight could resume the exact same sequence of moves to complete another tour) while if the knight is unable to hop to the original square, it is known as an open tour.
#include <iostream>
#include <iomanip>
#include <conio.h>
using namespace std;
void possible();
void exits(int);
const int ver[]={-1,-2,-2,-1,1,2,2,1},
hor[]={2,1,-1,-2,-2,-1,1,2};
int row,col,npos;
int board[8][8],nextij[8][8][8],accessible[8][8];
int main()
{
int count = 1,k,j;
cout <<"position [from (0,0) to (7,7)]:";
cin >>row >>col;
cout << endl;
board[row][col]=count;
while(count!=64)
{
count++;
possible();
exits(count);
}
for(j=0;j<=7;j++)
{
for(k=0;k<=7;k++)
cout << setw(3) << board[j][k];
cout <<"\n\n";
}
getch();
return 0;
}
void possible()
{
int npos;
for(int r=0;r<=7;r++)
{
for(int c=0;c<=7;c++)
{
npos = 0;
for(int i=0;i<=7;i++)
{
if(((r+ver[i] >=0) && (r+ver[i] <=7))&&((c+hor[i] >=0) && (c+hor[i] <=7))&&(board[r+ver[i]][c+hor[i]] == 0))
{
nextij[r][c][npos] = i;
npos++;
}
}
accessible[r][c] = npos;
}
}
}
void exits(int l)
{
int min = accessible[row+ver[nextij[row][col][0]]][col+hor[nextij[row][col][0]]];
int r = row+ver[nextij[row][col][0]],c=col+hor[nextij[row][col][0]];
for(int i=1;i < accessible[row][col];i++)
if(min >= accessible[row+ver[nextij[row][col][i]]][col+hor[nextij[row][col][i]]])
{
min =accessible[row+ver[nextij[row][col][i]]][col+hor[nextij[row][col][i]]];
r = row + ver[nextij[row][col][i]];
c = col + hor[nextij[row][col][i]];
}
//cout <<"\n min ="<<min <<" ("<<r<<','<<c<<") \n";
board[r][c]=l;
row = r;
col = c;
}Output of the C++ Program
position [from (0,0) to (7,7)]: 1 1 55 42 15 12 57 32 17 10 14 1 56 43 16 11 34 31 41 54 13 64 33 58 9 18 2 25 46 51 44 63 30 35 47 40 53 26 59 36 19 8 24 3 50 45 52 27 62 29 39 48 5 22 37 60 7 20 4 23 38 49 6 21 28 61
Feel free to explore and modify the code to understand how the knight’s tour algorithm works and experiment with different graphics libraries or interfaces for more interactive displays.
This code serves as a starting point for understanding basic graphics programming in C and implementing a solution to a classic chess problem.