// ** The Tour Of The Knight **
// To make the Knight move from any given starting square on the chessboard
// in such a manner that he touches each and every square of the chessboard
// only once . The problem is solved using the 'Warsndorff' Heuristic. 
// The Knight is moved to the square which is accessible from the least no. 
// of squares first . For instance , the corner squares are the least accessible,
// so the Knight tries to cover those as soon as possible.
// Initially if we mark each square of the chessboard with the number of squares it
// is accessible from the board looks like :
	2 3 4 4 4 4 3 2
	3 4 6 6 6 6 4 3
	4 6 8 8 8 8 6 4
        4 6 8 8 8 8 6 4
        4 6 8 8 8 8 6 4
        4 6 8 8 8 8 6 4
	3 4 6 6 6 6 4 3
	2 3 4 4 4 4 3 2
Every time a square is reached , the values in all the squares accessible are decreased by 1 .
(This method is known to produce solutions uptil 76x76 chessBoards )
---------------------------------------------------------------------------------------
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
typedef struct
{int x;
 int y;
}position;
position moveknight(position ,int moveNo);
void move(int chessBoard[][8]);
void displayBoard(int chessBoard[][8]);
int generateMove(int chessBoard[][8],position current);

int Access[8][8]={2,3,4,4,4,4,3,2,3,4,6,6,6,6,4,3,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,
		      4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,3,4,6,6,6,6,4,3,2,3,4,4,4,4,3,2};
int main()
{
int chessBoard[8][8]={0};
printf("\n\nTOUR OF THE KNIGHT :");
move(chessBoard); getchar(); getchar();
}
void move(int chessBoard[][8])
{position current,Pos,newpos;
int moveCtr=0,ctr1=0,flag=1,moveNo=0;
printf("\nEnter the X-Coordinate Of Starting Position.(between 1 & 8 ):");
scanf("%d",&current.x);
printf("\nEnter the Y-Coordinate Of Starting Position.(between 1 & 8 ):");
scanf("%d",&current.y);
current.x-- ; current.y--;
while(1){moveCtr++;
chessBoard[current.x][current.y]=moveCtr;
flag=1;
	for(ctr1=1;ctr1<=8;ctr1++)
		{Pos=moveknight(current,ctr1);
		if(Pos.x>=0&&Pos.y>=0&&Pos.x<8&&Pos.y<8)
		{Access[Pos.x][Pos.y]--;
		if(chessBoard[Pos.x][Pos.y]==0) flag=0;
		}
		};
if(flag==1)
	{if(moveCtr==64) printf("\nSolved! \n Final Situation:");
	 else printf("\nYou're Stuck !\n Final Situation:");
	 printf("\nOrder in which the Squares were visited.");
	 printf("\nValues are displayed in row-col order of the cells .");
	 displayBoard(chessBoard);
	 printf("\n (1 indicates the starting square & 64 indicates the last square visited . )");

	 goto lastline;
	 }
do{moveNo=generateMove(chessBoard,current);
  newpos=moveknight(current,moveNo);
  }while(newpos.x<0||newpos.y<0||newpos.x>7||newpos.y>7||chessBoard[newpos.x][newpos.y]!=0);
current=newpos;
};
lastline:
printf("\nBYE!");
return;
}

position moveknight(position currentPosition,int moveNo)
{position newPosition;
if(moveNo==1)
	{ newPosition.x=currentPosition.x+1;
  	newPosition.y=currentPosition.y+2;
	};
if(moveNo==2)
	{ newPosition.x=currentPosition.x+2;
  	newPosition.y=currentPosition.y+1;
	};

if(moveNo==3)
	{ newPosition.x=currentPosition.x+2;
 	 newPosition.y=currentPosition.y-1;
	};
if(moveNo==4)
	{ newPosition.x=currentPosition.x+1;
  	newPosition.y=currentPosition.y-2;
	};
if(moveNo==5)
	{ newPosition.x=currentPosition.x-1;
  	newPosition.y=currentPosition.y-2;
	};
if(moveNo==6)
	{ newPosition.x=currentPosition.x-2;
  	newPosition.y=currentPosition.y-1;
	};
if(moveNo==7)
	{ newPosition.x=currentPosition.x-2;
  	newPosition.y=currentPosition.y+1;
	};
if(moveNo==8)
	{ newPosition.x=currentPosition.x-1;
  	newPosition.y=currentPosition.y+2;
	};
return  newPosition;
}

void displayBoard(int chessBoard[][8])
{
int ctr1=0,ctr2=0;
printf("\n");
for(ctr1=7;ctr1>=0;ctr1--)
	{
	printf("\n");
	for(ctr2=0;ctr2<8;ctr2++)
	printf("\t%d",chessBoard[ctr2][ctr1]);
	}
}

int generateMove(int chessBoard[][8],position currentPosition)
{int ctr1,suitableMove,leastAcc;
 position Pos;
 ctr1=1;
 do
 {suitableMove=ctr1;
  Pos=moveknight(currentPosition,suitableMove);
  leastAcc=Access[Pos.x][Pos.y];
  ctr1++;
  }while((Pos.x)*(Pos.x-7)>0||Pos.y * (Pos.y-7)>0||chessBoard[Pos.x][Pos.y]!=0);
 for(ctr1=suitableMove+1;ctr1<9;ctr1++)
 { Pos=moveknight(currentPosition,ctr1);
   if((Pos.x)*(Pos.x-7)<=0&&Pos.y * (Pos.y-7)<=0&&chessBoard[Pos.x][Pos.y]==0)
   if(Access[Pos.x][Pos.y]<leastAcc)
    {suitableMove=ctr1;
     leastAcc=Access[Pos.x][Pos.y];
    }
 }
 return suitableMove ;

}