#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define N 6  //棋盘的大小
int jump(int i,int j,int a[N][N],int);//可以向a[i][j]跳一步，就是把a[i][j]赋值
void horse(int ,int ,int,int [][N]);//递归主程序
void outplan(int a[N][N]);//把最后的结果输出

int x,y;
void  copy(int[][N],int [][N]);
//程序构造了两个棋盘save[N][N],sum[N][N],主要是为了回溯的时候用
main(){


 printf("Please input start position:");
 //printf("%2d",N*N);
 printf("\n");
 scanf("%d%d",&x,&y); //输入起始位置
 int sum[N][N]={0};
 int times=1;
 sum[x-1][y-1]=0;
 //outplan(sum);
 horse(x-1,y-1,times,sum);//运行递归程序
 system("pause");
}
void horse(int i,int j,int times,int sum[][N]){
 
 int h[]={1,2,2,1,-1,-2,-2,-1},//构造八个方向的走法
     v[]={2,1,-1,-2,2,1,-1,-2},
   save[N][N],ti=0,tj=0,count=0,kk=0;
   
    if(times==N*N+1/*&&check(i,j)*/)
        outplan(sum);//输出结果
      
      else{
        copy(save,sum);  //构造另一个棋盘
       for(count=0; count<=7 ;count++){
          ti=i+h[count];                 
          tj=j+v[count];
         
          if(jump(ti,tj,save,times)){  //检验并且下子
           
            kk=times+1;  
            horse(ti,tj,kk,save); //递归执行
            save[ti][tj]=0;  //回溯以后，恢复原值
                                     }
                                       }
          }                           
}
int jump(int i,int j,int a[N][N],int times)
{
 if(i<N&&i>=0&&j<N&&j>=0&&a[i][j]==0){
     a[i][j]=times;                                 
     return 1;
     }
 return 0;
}
void outplan(int a[N][N]){
 int i,j;
 for(i=0;i<N;i++){
  for(j=0;j<N;j++)
   printf("%3d",a[i][j]);
  printf("\n");
 }
 
 printf("\n");
 system("pause");
 //getchar();
}
void  copy(int save[][N],int sum[][N])
{
      for(int i=0;i<=N-1;i++)
        for(int j=0;j<=N-1;j++)
           save[i][j]=sum[i][j];
}