mtqp1.c

马踏棋盘的源程序！实现国际象棋中马走遍整个棋盘！

#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]={0};/* 8*8的方正棋盘,为后来保存步数*/
int a[N*N+1][3]={0};
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<1||i>8||j<1||j>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("\n------%d answer----\n",++w);
 
 for(x=1;x<N+1;x++)
 {
  printf("\n");
  for(y=1;y<N+1;y++)
   printf("%2d ",ch[(x-1)*N+y-1]);
  printf("\n");
 }
 printf("\nPress n to quit ,press any other key to continue.\n");

 c=getchar();        /*询问是否继续输出结果*/
}

main()   
{
 int x,y,way,way0;
 caculate();
 directions();
 printf("Please enter the row and column of the starting point.\n");
 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<1||y<1||x>N||y>N||ch[(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--;                      /*退回前一步*/
   }
  }
 }
}