对马踏棋盘的一点研究

核心提示： /*对马踏棋盘的一点研究*//* QQ：164094487 *//* Email: fygood@163.com *//*欢迎与我联系，讨论问题 *//*本人先后编了两次，对马踏棋盘的一点研究，第二次进行了改进，改进的思想主要是注重到棋盘上每一点的下一可到达点的个数（下称为权值）不同，而m方向可达到*/ (

 /*对马踏棋盘的一点研究*/
/* 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<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--;　　　　　　　　　　  /*退回前一步*/
　 }
　}
 }
}
/*
第二次： 改进后的马踏棋盘，加入了每点的权值因素，速度极快*/
#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<N;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<N;i++)
　 for(j=0;j<N;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<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,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--;　　　　　　　　　　  /*退回前一步*/
　 }
　}
 }
}