Answered by:
Evaluate this program (Knight's Tour )...

Question
-
One more program from for you guys to evaluate...
This is my own program. Suggestions for improvements are welcome. Mail me at raghuramdcbe@gmail.com . Program Copyrighted. USE TurboC compiler for execution of the program
Code Snippet#include
<conio.h>#include
<stdio.h>int
chessBoard[8][8],c=0,d=1,code,flag=0,returnt=0;float
del=1;double
sim=0,solution=0.0;int
acc[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}};char
str[100];void
print(int type);void
mnuMain();void
mnu();void
mnu1();void
revert(int e,int f);void
delay();void
mnuTour(int s[]);void
placeKnight(int e,int f);int
findPos(int i,int j,int avbPos[8][2]);int
num();void
revert(int e,int f);void
delay();void
main(){
int a=0,b=0,s[2]={0,0};c=0;
d=1;
flag=0;
returnt=0;
del=1;
sim=solution=0.0;
mnuMain();
if(returnt==1) return;clrscr();
mnuTour(s);
for(a=s[0];a<8;a++) for(b=s[1];b<8;b++){
if(returnt==1) return;placeKnight(a,b);
}
if(solution==0.0)printf(
"\n\n\nNo solution exists for the selection\n");getch();
}
void
mnuTour(int s[]){
int tour; char ch;clrscr();
printf(
"\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s",str);printf(
"\n\n\n1. All tours \n2. Tours from specific location\n\n");printf(
"Enter the option : ");get:
ch=getche();
if(!(ch==49||ch==50)){
printf(
"\b \b"); goto get;}
elsetour=ch-48;
if(tour==2){
printf(
"\nEnter the x-coordinate of the position (0 to 7): ");startx:
ch=getche();
if(!(ch>=48&&ch<=55)){
printf(
"\b \b"); goto startx;}
elses[0]=ch-48;
printf(
"\nEnter the y-coordinate of the position (0 to 7): ");starty:
ch=getche();
if(!(ch>=48&&ch<=55)){
printf(
"\b \b"); goto startx;}
elses[1]=ch-48;
}
return;}
void
mnuMain(){
char ch;clrscr();
printf(
"\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t");printf(
"\n\nSelect a option \n\n1. All tours \n2. Closed tours\n3. Open tours\n4. Exit\n\n\n");printf(
"Enter the option : ");st1:
ch=getche();
if(!(ch>48&&ch<53)){
printf(
"\b \b"); goto st1;}
elsecode=ch-48;
switch(code){
case 1:strcpy(str,
"ALL KNIGHT'S TOURS"); break; case 2:strcpy(str,
"CLOSED KNIGHT'S TOURS"); break; case 3:strcpy(str,
"OPEN KNIGHT'S TOURS"); break; case 4:returnt=1;
}
}
void
mnu(){
int x,y,i,j,fl=1; for(x=0;x<8&&fl==1;x++){
for(y=0;y<8&&fl==1;y++){
if(chessBoard[x][y]==1){
i=x;
j=y;
fl=0;
}
}
}
if((i>1 && j<7 && chessBoard[i-2][j+1]==64)|(i>1 && j>0 && chessBoard[i-2][j-1]==64)|(i>0 && j<6 && chessBoard[i-1][j+2]==64)|(i>0 && j>1 && chessBoard[i-1][j-2]==64)|(i<6 && j<7 && chessBoard[i+2][j+1]==64)|(i<6 && j>0 && chessBoard[i+2][j-1]==64)|(i<7 && j<6 && chessBoard[i+1][j+2]==64)|(i<7 && j>1 && chessBoard[i+1][j-2]==64))fl=1;
elsefl=0;
switch(code){
case 1:mnu1();
break; case 2: if(fl==1)mnu1();
break; case 3: if(fl==0)mnu1();
break;}
}
void
mnu1(){
char ch; int type;printf(
"\n\nDo you want to view as \n\n1. Complete Solution \n2. Step by Step moves (Automated) \n3. Step by Step moves (Keypress)\n\n ");printf(
"\nEnter your option : ");st2:
ch=getche();
if(!(ch>48&&ch<52)){
printf(
"\b \b"); goto st2;}
elsetype=ch-48;
if(type==2){
printf(
"\nEnter the delay between successive steps in seconds : ");scanf(
"%f",&del);}
print(type);
gotoxy(20,35);
printf(
"\n\n\nDo you want to continue to view the other paths(Y/N) : ");st:
ch=getche();
if(!(ch=='y'||ch=='Y'||ch=='n'||ch=='N')){
printf(
"\b \b"); goto st;}
if(ch=='y'||ch=='Y') return; elsereturnt=1;
}
void
placeKnight(int e,int f){
int g,l,n,avbPos[8][2]; if(c==0){
for(g=0;g<8;g++) for(l=0;l<8;l++)chessBoard[g][l]=0;
c=1;
}
n=findPos(e,f,avbPos);
if(n==0){
if(d==64){
chessBoard[e][f]=d;
mnu();
if(returnt==1) return;sim++;
return;}
else return;}
else{
chessBoard[e][f]=num();
d++;
}
for(g=0;g<n;g++){
if(returnt==1) return;placeKnight(avbPos[g][0],avbPos[g][1]);
}
if(returnt==1) return;revert(e,f);
chessBoard[e][f]=0;
d--;
return;}
int
findPos(int i,int j,int avbPos[8][2]){
int k=0,Pos[8][2],x,y,n=0; if(i>1 && j<7 && chessBoard[i-2][j+1]==0){
Pos[k][0]=i-2;
Pos[k][1]=j+1;
k++;
}
if(i>1 && j>0 && chessBoard[i-2][j-1]==0){
Pos[k][0]=i-2;
Pos[k][1]=j-1;
k++;
}
if(i>0 && j<6 && chessBoard[i-1][j+2]==0){
Pos[k][0]=i-1;
Pos[k][1]=j+2;
k++;
}
if(i>0 && j>1 && chessBoard[i-1][j-2]==0){
Pos[k][0]=i-1;
Pos[k][1]=j-2;
k++;
}
if(i<6 && j<7 && chessBoard[i+2][j+1]==0){
Pos[k][0]=i+2;
Pos[k][1]=j+1;
k++;
}
if(i<6 && j>0 && chessBoard[i+2][j-1]==0){
Pos[k][0]=i+2;
Pos[k][1]=j-1;
k++;
}
if(i<7 && j<6 && chessBoard[i+1][j+2]==0){
Pos[k][0]=i+1;
Pos[k][1]=j+2;
k++;
}
if(i<7 && j>1 && chessBoard[i+1][j-2]==0){
Pos[k][0]=i+1;
Pos[k][1]=j-2;
k++;
}
y=acc[Pos[0][0]][Pos[0][1]];
for(x=1;x<k;x++) if(y>acc[Pos[x][0]][Pos[x][1]])y=acc[Pos[x][0]][Pos[x][1]];
for(x=0;x<k;x++) if(y==acc[Pos[x][0]][Pos[x][1]]){
avbPos[n][0]=Pos[x][0];
avbPos[n][1]=Pos[x][1];
n++;
}
return n;}
int
num(){
return d;}
void
revert(int e,int f){
int i,j,k; for(i=0;i<8;i++){
for(j=0;j<8;j++){
if(chessBoard[i][j]>chessBoard[e][f])chessBoard[i][j]=0;
}
}
}
void
delay(){
int i,j;gotoxy(1,1);
j=2*del;
for(;j>=0;j--) for(i=16000;i>0;i--)printf(
" \b");printf(
"\b");}
void
print(int type){
int x,y,i;solution++;
clrscr();
printf(
"\n\n\t\t\t\tKNIGHT'S TOUR PUZZLE \n");printf(
"\n\nProgrammer : Raghuram Duraisamy\n\n");printf(
"Email ID : Raghuramdcbe@gmail.com ");printf(
",raghusar_9000@hotmail.com");printf(
"\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s\n\n",str);printf(
"\n\n\n\t\t"); for(x=0;x<42;x++)printf(
"-");printf(
"\t\t \n\t\t"); switch(type){
case 1: for(x=0;x<8;x++){
for(y=0;y<8;y++){
if(y==7)printf(
"|%4d ",chessBoard[x][y]); elseprintf(
"|%3d ",chessBoard[x][y]);}
printf(
"|\t\t \n\t\t|"); for(y=0;y<7;y++)printf(
"----|");printf(
"-----|"); if(x!=7)printf(
"\t\t \n\t\t"); elseprintf(
"\t\t \n");}
break; case 2: case 3: for(i=1;i<=64;i++){
clrscr();
printf(
"\n");printf(
"\n\n\t\t\t\tKNIGHT'S TOUR PUZZLE \n");printf(
"\n\nProgrammer : Raghuram Duraisamy\n\n");printf(
"Email ID : Raghuramdcbe@gmail.com ");printf(
",raghusar_9000@hotmail.com");printf(
"\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s",str);printf(
"\n\n\n\t\t"); for(x=0;x<41;x++)printf(
"-");printf(
"\t\t \n\t\t"); for(x=0;x<8;x++){
for(y=0;y<8;y++){
if(chessBoard[x][y]<=i){
if(y==7)printf(
"|%4d ",chessBoard[x][y]); elseprintf(
"|%3d ",chessBoard[x][y]);}
else{
if(y==7)printf(
"| ",chessBoard[x][y]); elseprintf(
"| ",chessBoard[x][y]);}
}
printf(
"\b|\t\t \n\t\t|"); for(y=0;y<8;y++)printf(
"----|"); if(x!=7)printf(
"\t\t \n\t\t"); elseprintf(
"\t\t \n");}
if(type==2)delay();
elsegetch();
}
break;}
}
Tuesday, June 5, 2007 12:52 PM
Answers
-
A knight's tour of a chessboard is a sequence of moves by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the graphs consisting of vertices corresponding to the chessboard squares and edges corresponding to legal knight moves. If the final position of such a tour is a knight's move away from the initial position of the knight, the tour is called re-entrant or closed, and is therefore a Hamiltonian circuit. Else the tour is called a open tour.
Tuesday, June 5, 2007 12:53 PM -
I have seen a whitepaper of this same puzzle posted by someone else. Dont remember name. I dont know why people wont even bother to change the contents, and replace their names.Wednesday, June 6, 2007 2:15 PM
-
Yes... If they don't even know what they post in the in their papers, how blindly are these persons rushing for points??
I really wonder...
Thursday, June 7, 2007 2:32 AM -
The admins should take care of themThursday, June 7, 2007 6:05 AM
All replies
-
A knight's tour of a chessboard is a sequence of moves by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the graphs consisting of vertices corresponding to the chessboard squares and edges corresponding to legal knight moves. If the final position of such a tour is a knight's move away from the initial position of the knight, the tour is called re-entrant or closed, and is therefore a Hamiltonian circuit. Else the tour is called a open tour.
Tuesday, June 5, 2007 12:53 PM -
I have seen a whitepaper of this same puzzle posted by someone else. Dont remember name. I dont know why people wont even bother to change the contents, and replace their names.Wednesday, June 6, 2007 2:15 PM
-
Yes... If they don't even know what they post in the in their papers, how blindly are these persons rushing for points??
I really wonder...
Thursday, June 7, 2007 2:32 AM -
The admins should take care of themThursday, June 7, 2007 6:05 AM