对马踏棋盘的一点研究
/*对马踏棋盘的一点研究*/
/* QQ：164094487 */
/* Email: fygood@163.com */
/*欢迎与我联系，讨论问题 */
/*本人先后编了两次，第二次进行了改进。改进的思想主要是注重到棋盘上每一点的下一可到达点的个数
（下称为权值）不同，对于可到达点较少（权值小）的点应该先跳上去，这样后来跳的点可跳的方向就比
较多，回溯的现象就比较少，这样就可以大幅度提高速度*/
/*第一次*/
/*原始的马踏棋盘，未加权值，有些点速度很慢*/
#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 { printf(" "); for(y=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--; /*退回前一步*/ } } } } /* 第二次： 改进后的马踏棋盘，加入了每点的权值因素，速度极快*/ #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 dir[N][N][8]; int st=1; char c='y'; int weight[N][N]; void caculate(); void dirctions(); void print(); int check(int i,int j); void caculate() /*计算各点的权值*/ { int i,j,k; for(i=1;i<=N;i++) for(j=1;j<=N;j++) for(k=0;k { int x,y; x=i+way1[k]; y=j+way2[k]; if(x>=1&&x<=N&&y>=1&&y<=N) weight[i-1][j-1]++; } } int check(int i,int j) /*检查(i,j)是否在棋盘内*/ { if(i<1i>8j<1j>8) return 0; return 1; } void directions() /*求出各点的最佳方向序列，即优先向权值小的方向*/ { int i,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2; for(i=0;i for(j=0;j { for(k=0;k<8;k++) dir[i][j][k]=k; for(k=0;k<8;k++) { for(m=k+1;m<8;m++) /*对每个方向考察看有没有更好的*/ { way_1=dir[i][j][k]; x1=i+way1[way_1]; y1=j+way2[way_1]; way_2=dir[i][j][m]; x2=i+way1[way_2]; y2=j+way2[way_2]; n1=check(x1+1,y1+1); n2=check(x2+1,y2+1); if( ( n1==0 && n2 ) /*k方向不可达到，而m方向可达到*/ ( n1 && n2&&weight[x1][y1]>weight[x2][y2] )/*都可达到但m方向权值小*/ ) { dir[i][j][k]=way_2; dir[i][j][m]=way_1; /*交换两个方向值*/ } } } } } void print() { int x,y; printf(" ------%d answer---- ",++w); for(x=1;x { printf(" "); for(y=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,way0; caculate(); directions(); 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 /*此点的八个方向未全走过，应走此方向*/ { way0=a[st][2]; a[st][2]++; /*确定下次应走的方向*/ x=a[st][0]; y=a[st][1]; way=dir[x-1][y-1][way0]; 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--; /*退回前一步*/ } } } }
