Today, let's talk about a problem related to the N-Queens problem, the Knight's traversal problem, or the horse traversal problem in chess. Of course, here we are talking about the knight in international chess. There are many similarities between the two, but also many differences, mainly in terms of path restrictions. The N-Queens problem mainly involves freely placing queens as long as the conditions are met, while the knight's traversal problem is related to the paths of up and down traversal. It mainly uses graph algorithms such as depth-first search and breadth-first search, as well as algorithms for constructing graphs.
Requirements: Implement a knight chess piece on any position on the chessboard, making sure it does not repeat any square on the chessboard.
Analysis: First, we need to know how the knight moves on the chessboard. According to the rules of international chess, the knight has 8 available moves from a starting position, of course, with additional considerations for the boundaries. Our knight's movement must consider these 8 possibilities, excluding positions that cannot be used and moving to available positions. When all 8 positions are not available, we need to consider going back to the previous step, which is similar to breadth-first traversal in graphs. The traversal ends when the knight has visited all positions and there are no available positions to move to.
Analysis complete, the code is as follows. If you have any questions, please leave a comment:
/*Knight's traversal problem
*2008 12 28 CG
**/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
int f[11][11] ;
int adjm[121][121];
long fgf;
int n,m;
int es(int i1,int j1,int i2,int j2){
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;/*Establish path connections*/
}/*es*/
int creatadjm(){/*Draw the graph of available paths*/
int i,j;
for(i=1;i< =n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;/*Initialize path records*/
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm[i][j]=0;/*Initialize chessboard*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0){/*Set valid paths*/
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) es(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) es(i,j,i+2,j-1);
if((i-2>=1)&&(j+1< =n)) es(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) es(i,j,i-2,j-1);
if((j+2< =n)&&(i+1<=n)) es(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) es(i,j,i-1,j+2);
if((j-2>=1)&&(i+1< =n)) es(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) es(i,j,i-1,j-2);
}/*if*/
return 1;
}/*createadjm*/
int travel(int p,int r){/*Knight's traversal*/
int i,j,q;
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ;j++)
if(f[i][j] > r)/*Meets the requirements?*/
f[i][j]=0;
r = r + 1;
i=((p-1) / n) + 1;
j=((p-1) % n) + 1;
f[i][j] = r;
fgf++;/*Record path selection*/
for(q = 1 ; q < = m ; q++){
i=((q-1) / n) + 1;
j=((q-1) % n) + 1;
if((adjm[p][q] == 1) && (f[i][j] == 0))
travel(q , r);/*Recursive traversal*/
}/*for*/
return 1;
}/*travel*/
int main(){
int i,j,k,l;
clrscr();
printf("Input chessboard size n:");scanf("%d",&n);/* Enter the size of the chessboard, maximum 11*/
m = n * n;
creatadjm();/*Draw available paths*/
/*Output available paths
for(i=1;i<=m;i++){/*Output*/
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("n");
}
getchar();
*/
printf("Input a start post i,j:");/*Enter the starting point for traversal*/
scanf("%d %d",&i,&j);
l = (i - 1) * n + j;
while ((i > 0) || (j > 0)){/*Loop until input is 0 0*/
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ; j++)
f[i][j] = 0;/*Initialize path records*/
k = 0;
travel(l , k);/*Traversal*/
printf("select: %d pathnfinal path",fgf);/*Output the number of path selections*/
fgf=0;/*Reset to zero*/
for(i = 1 ; i <= n ; i++){/*Output traversal path*/
for(j = 1 ; j <= n ; j++)
printf("%4d",f[i][j]);
printf("n");
}
printf("Input a start post i,j:");scanf("%d %d",&i,&j);/*Continue input*/
l = (i - 1) * n + j;
}/*while*/
return 0;
}/*main*/