/*对马踏棋盘的一点研究*/
/* QQ：164094487 */
/* Email: [email protected] */
/*欢迎与我联系，讨论问题 */
/*本人先后编了两次，第二次进行了改进。改进的思想主要是注意到棋盘上每一点的下一可到达点的个数
（下称为权值）不同，对于可到达点较少（权值小）的点应该先跳上去，这样后来跳的点可跳的方向就比
较多，回溯的现象就比较少，这样就可以大幅度提高速度*/
/*第一次*/
/*原始的马踏棋盘，未加权值，有些点速度很慢*/
#include "stdio.h"
#define N 8
int w=0;
int way1[8]={-2,-1,1,2, 2, 1,-1,-2};
int way2[8]={ 1,2, 2,1,-1,-2,-2,-1};
int ch[N*N]=;
int a[N*N+1][3]=;
int st=1;
char c='y';
void print()
{
int x,y;
printf(" ------%d answer---- ",++w);
for(x=1;x<N+1;x++)
{
printf(" ");
for(y=1;y<N+1;y++)
printf("%2d ",ch[(x-1)*N+y-1]);
printf(" ");
}
printf(" Press n to quit ,press any other key to continue. ");
c=getchar(); /*询问是否继续输出结果*/
}
main()
{
int x,y,way;
printf("Please enter the row and column of the starting point. ");
scanf("%d,%d",&a[1][0],&a[1][1]);/*输入行数和列数*/
getchar(); /*接收回车符*/
x=a[1][0],y=a[1][1];
ch[(x-1)*N+y-1]=1; /*在ch数组中对相应点赋值*/
while(1)
{
if(a[1][2]>=8) /*出发点的八个方向都已走过，表示所有的方法均已找出*/
break;
if(a[st][2]>=8) /*此点的八个方向都已走过，应该退回到上一次走的点*/
{
x=a[st][0];
y=a[st][1];
ch[(x-1)*N+y-1]=0; /*将这一点被走过的痕迹抹去*/
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++; /*使上一次走的点走的方向发生变化*/
st--; /*步数减一*/
}
else /*此点的八个方向未全走过，应走此方向*/
{
way=a[st][2];
a[st][2]++; /*确定下次应走的方向*/
x=a[st][0]+way1[way];
y=a[st][1]+way2[way]; /*确定按这次的方向走应走到的x,y坐标*/
if(x<1y<1x>Ny>Nch[(x-1)*N+y-1]!=0)/*此点不满足要求*/
continue;
ch[(x-1)*N+y-1]=++st; /*走到这一点 */
a[st][0]=x;
a[st][1]=y;
a[st][2]=0; /*标记这一步*/
if(st==N*N) /*步数已满*/
{
print(); /*输出结果*/
if(c=='n')
break;
ch[(x-1)*N+y-1]=0;
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++;
st--; /*退回前一步*/
}
}
}
}