马踏棋盘问题

核心提示：#include <stdio.h>#define N 5void main(){ int x,y; void horse(int i,int j); PRintf("Please input start position:"); scanf("%d%d",&x,&y

#include <stdio.h>
#define N 5
void main(){
 int x,y;
 void horse(int i,int j);
 PRintf("Please input start position:");
 scanf("%d%d",&x,&y);
 horse(x-1,y-1);
}
void horse(int i,int j){
 int a[N][N]={0},start=0,
　h[]={1,2,2,1,-1,-2,-2,-1},
　v[]={2,1,-1,-2,2,1,-1,-2},
　save[N*N]={0},posnum=0,ti,tj,count=0;
 int jump(int i,int j,int a[N][N]);
 void outplan(int a[N][N]);
 a[i][j]=posnum+1;
 while(posnum>=0){
　ti=i;tj=j;
　for(start=save[posnum];start<8;++start){
　 ti+=h[start];tj+=v[start];
　 if(jump(ti,tj,a))
　　break;
　 ti-=h[start];tj-=v[start];
　}
　if(start<8){
　 save[posnum]=start;
　 a[ti][tj]=++posnum+1;
　 i=ti;j=tj;save[posnum]=0;
　 if(posnum==N*N-1){
　　//outplan(a);
　　count++;
　 }
　}
　else{
　 a[i][j]=0;
　 posnum--;
　 i-=h[save[posnum>;j-=v[save[posnum>;
　 save[posnum]++;
　}
 }
 printf("%5d",count);
}
int jump(int i,int j,int a[N][N]){
 if(i<N&&i>=0&&j<N&&j>=0&&a[i][j]==0)
　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");
 //getchar();
}
用回溯法得到所有的解，但效率较低，只能算出5行5列的。