马踏棋盘问题

#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列的。