骑士巡游问题
国际象棋为许多令人着迷的娱乐提供了固定的框架，这些框架独立于游戏本身。其中很多都是基于奇异的骑士“L 型”（L-shaped）移动。一个经典的例子就是骑士巡游（knight's tour）问题，自从十八世纪初以来，这个问题吸引了数学家们的兴趣，也使热心者们感到困惑。简而言之，这个问题要求从棋盘上任意给定的方格开始移动骑士，相继地到达所有的64 个方格，进入每个方格一次且仅进入一次。通常情况下，我们用如下方法表示一个解：即把数字0，1，…，63
放入棋盘中的方格来表示到达这些方格的顺序。解决骑士巡游问题更具创意的方法之一是由J. C. Warnsdorff 在1823 年提出的。其规则是：骑士总是移向具有最少出口且没有到达过的方格之一。
基本要求：
(1) 使用Warnsdorff 规则，设计并实现解决骑士巡游问题的算法；
(2) 打印棋盘，并显示骑士巡游问题的解，动态地标注行走过程。
(3) 程序能方便地地移植到其它规格的棋盘上。
实现提示：
① 用一个二维数组表示国际象棋棋盘；
② 骑士的八种可能移动表示：如果骑士当前位于方格（i，j），则骑士可能移到
的方格有（i– 2，j + 1），（i - 1，j + 2），（i + 1，j + 2），（i + 2，j + 1），
（i + 2，j - 1）（i + 1，j -2），（i - 1，j - 2），（i - 2，j - 1）。然而，
我们注意到，如果（i，j）处于接近棋盘的边缘方格，在这些可能的移动中，有
些移动就会使骑士移出棋盘，这当然是不允许的。我们可以很容易地使用两个数
组ktmove1 和ktmove2 把骑士的八种可能移动表示为：
ktmove1 ktmove2
-2 1
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
于是，位于（i，j）的骑士就可能移到（i + ktmove1[k]，j + ktmove2[k]），
其中k 是介于0 和7 之间的某个值，且假定新方块仍然位于棋盘上。
4.1 重要程序段1
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define M 8//宏定义棋盘大小
#define SIZE 100
int qipan[M][M];//表示要到这个格子的步数
typedef struct direct
{int x,y,direction ;//在棋盘中的位置坐标x,y及结点可走方向数目 direction
}dir ;
4.2 重要程序段2
int direction(int row,int cn)//用来计算当前位置可走的方向数目
{int a,b,count=0 ;//count来计数a=row ;b=cn ;if(a-2>=0&&b-1>=0&&qipan[a-2][b-1]==0)//不出界并且未走过count++;if(a-2>=0&&b+1<M&&qipan[a-2][b+1]==0)count++;if(a+2<M&&b-1>=0&&qipan[a+2][b-1]==0)count++;if(a+2<M&&b+1<M&&qipan[a+2][b+1]==0)count++;if(a-1>=0&&b+2<M&&qipan[a-1][b+2]==0)count++;if(a-1>=0&&b-2>=0&&qipan[a-1][b-2]==0)count++;if(a+1<M&&b+2<M&&qipan[a+1][b+2]==0)count++;if(a+1<M&&b-2>=0&&qipan[a+1][b-2]==0)count++;return count ;
}
4.3 重要程序段3
void findway(int m,int n)//寻找路径函数
{dir f[8],path ;int i,j,k, step ;//stemnum表示步数step=1 ;i=m ;j=n ;while(step<M*M&&i<M&&j<M&&i>=0&&j>=0){qipan[i][j]=step ;if(step%6==0)printf("\\n");printf("(%d,%d) --> ",i,j);//输出走的格子path.direction=8 ;//用来标志可走方向数的最小值 for(k=0;k<8;k++)//对方向数组赋初值{f[k].x=-1 ;f[k].y=-1 ;}//结构体数组f【】用来存放可走的方向点以及下一次可走的方向数if(i-2>=0&&j-1>=0){f[0].x=i-2 ;f[0].y=j-1 ;f[0].direction=direction(f[0].x,f[0].y);}if(i-2>=0&&j+1<M){f[1].x=i-2 ;f[1].y=j+1 ;f[1].direction=direction(f[1].x,f[1].y);}if(i+2<M&&j-1>=0){f[2].x=i+2 ;f[2].y=j-1 ;f[2].direction=direction(f[2].x,f[2].y);}if(i+2<M&&j+1<M){f[3].x=i+2 ;f[3].y=j+1 ;f[3].direction=direction(f[3].x,f[3].y);}if(i-1>=0&&j+2<M){f[4].x=i-1 ;f[4].y=j+2 ;f[4].direction=direction(f[4].x,f[4].y);}if(i-1>=0&&j-2>=0){f[5].x=i-1 ;f[5].y=j-2 ;f[5].direction=direction(f[5].x,f[5].y);}if(i+1<M&&j-2>=0){f[6].x=i+1 ;f[6].y=j-2 ;f[6].direction=direction(f[6].x,f[6].y);}if(i+1<M&&j+2<M){f[7].x=i+1 ;f[7].y=j+2 ;f[7].direction=direction(f[7].x,f[7].y);}for(k=0;k<8;k++)//寻找当前位置的八个方向中的可走方向数最少的方向作为新的方向if(f[k].x>=0&&f[k].y>=0&&f[k].direction<=path.direction&&qipan[f[k].x][f[k].y]==0&&f[k].direction>0){path.direction=f[k].direction;path.x=f[k].x ;path.y=f[k].y ;}i=path.x ;//数组里的x，y作为新的i和jj=path.y ;step++;}//找不到后跳出循环if(i-2>=0&&j-1>=0&&qipan[i-2][j-1]==0){i=i-2 ;j=j-1 ;}else if(i-2>=0&&j+1<M&&qipan[i-2][j+1]==0){i=i-2 ;j=j+1 ;}else if(i-1>=0&&j+2<M&&qipan[i-1][j+2]==0){i=i-1 ;j=j+2 ;}else if(i+1<M&&j+2<M&&qipan[i+1][j+2]==0){i=i+1 ;j=j+2 ;}else if(j+2<M&&i+1<=M&&qipan[i+2][j+1]==0){i=i+2 ;j=j+1 ;}else if(i+2<M&&j-1>=0&&qipan[i+2][j-1]==0){i=i+2 ;j=j-1 ;}else if(i+1<M&&j-2>=0&&qipan[i+1][j-2]==0){i=i+1 ;j=j-2 ;}else if(i-1>=0&&j-2>=0&&qipan[i-1][j-2]==0){i=i-1 ;j=j-2 ;} qipan[i][j]=M*M ;printf("(%d,%d)",i,j);
}
4.4 重要程序段4
void main()
{int x,y,i,j ;printf("-----------------欢迎进入马踏棋盘系统！-----------------\\n");printf("棋盘为8*8，坐标为0~7\\n");printf("请输入马在棋盘上的x坐标：x=");scanf("%d",&x);printf("请输入马在棋盘上的y坐标：y=");scanf("%d",&y);findway(x,y);printf("\\n");printf("输出整个棋盘的步骤：\\n");for(i=0;i<M;i++)//输出棋盘上的路径{for(j=0;j<M;j++)printf("%3d",qipan[i][j]);printf("\\n");}
}