knight tour Algorithm
If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open. A knight's tour is a sequence of movements of a knight on a chessboard A tour reported in the fifth book of Bhagavantabaskaraby by Bhat Nilakantha, a cyclopedic work in Sanskrit on ritual, law and politics, write either about 1600 or about 1700 describes three knight's tours.
The Sri Vaishnava poet and philosopher Vedanta Desika during 14th century in his 1,008-verse magnum opus praising lord Ranganatha's divine sandals of Srirangam, i.e. Paduka Sahasram (in chapter 30: Chitra Paddhati) has composed two consecutive Sanskrit verses containing 32 letters each (in Anushtubh meter) where the second verse can be derived from the first verse by performing Knight's tour on a 4 × 8 board, beginning from the top-leave corner. It is believed that Desika composed all 1008 verses (including the special Chaturanga Turanga Padabandham noted above) in a individual night as a challenge.
#include <iostream>
# define n 8
/**
A knight's tour is a sequence of moves of a knight on a chessboard
such that the knight visits every square only once. If the knight
ends on a square that is one knight's move from the beginning
square (so that it could tour the board again immediately, following
the same path), the tour is closed; otherwise, it is open.
**/
using namespace std;
bool issafe(int x,int y,int sol[n][n])
{
return (x<n && x>=0 && y<n && y>=0 && sol[x][y]==-1);
}
bool solve(int x,int y, int mov, int sol[n][n], int xmov[n], int ymov[n])
{
int k,xnext,ynext;
if(mov == n*n)
return true;
for(k=0;k<8;k++)
{
xnext=x+xmov[k];
ynext=y+ymov[k];
if(issafe(xnext,ynext,sol))
{
sol[xnext][ynext]=mov;
if(solve(xnext,ynext,mov+1,sol,xmov,ymov)==true)
return true;
else
sol[xnext][ynext]=-1;
}
}
return false;
}
int main()
{
//initialize();
int sol[n][n];
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
sol[i][j]=-1;
int xmov[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int ymov[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
sol[0][0]=0;
bool flag=solve(0,0,1,sol,xmov,ymov);
if(flag==false)
cout<<"solution doesnot exist \n";
else
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<sol[i][j]<<" ";
cout<<"\n";
}
}
}
