Chess – Knight’s Tour Implementation in C++

Knight's tour - C++ Implementation

Knight's tour

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.

M. Saqib: Saqib is Master-level Senior Software Engineer with over 14 years of experience in designing and developing large-scale software and web applications. He has more than eight years experience of leading software development teams. Saqib provides consultancy to develop software systems and web services for Fortune 500 companies. He has hands-on experience in C/C++ Java, JavaScript, PHP and .NET Technologies. Saqib owns and write contents on mycplus.com since 2004.
Related Post