/*
Name: 跳马问题
Copyright:
Author:
Date: 04-12-04 17:46
Description:
*/
#include<stdio.h>
#define SIZE 5
int row[8]={1,2,2,1,-1,-2,-2,-1};/*8个方向上的x增量*/
int col[8]={-2,-1,1,2,2,1,-1,-2}; /*8个方向上的y增量*/
int h[SIZE][SIZE];/*记录走的路径*/
int num;/*记录方案个数*/
void printSolution();
void try(int,int,int);
void try1(int x,int y,int i);
main()
{
int row,col;
/*初始化*/
num=0;
for(row=0;row<=SIZE-1;row++)
for(col=0;col<=SIZE-1;col++)
h[row][col]=0;
/*占据位置（0,0）*/
h[0][0]=1;
/*从(0,0)出发，寻找后续位置*/
try1(0,0,2);
/*输出总方案数*/
printf("总方案数为%d",num);
system("pause");
}
/*函数功能：从step[i-1]出发，求(step[i]~step[SIZE*SIZE])。step[i-1]坐标为（x，y） */
void try(int x,int y,int i)
{
int dir,u,v;
for(dir=0;dir<=7;dir++){ /*依次试遍8个方向*/
u=x+row[dir]; /*得到的新坐标*/
v=y+col[dir];
if ((u>=0) && (u<=SIZE-1) && (v>=0) && (v<=SIZE-1) && (h[u][v]==0)){/*如果新坐标在棋盘上，并且这一格可以走*/
h[u][v]=i;/*占据位置[u,v]*/
if(i==SIZE*SIZE){ /*已经走完25步，则统计方案个数，打印方案，跳出递归*/
num++;
if (num<=3)/*打印前3种方案*/
printSolution();
}
else
try(u,v,i+1); // 从step[i]出发，求(step[i+1]~step[SIZE*SIZE])
h[u][v]=0;//清空位置
}
}
}
/*函数功能：从step[i-1]出发，求(step[i]~step[SIZE*SIZE])。step[i-1]坐标为（x，y） */
void try1(int x,int y,int i)
{
int dir,u,v;
if (i>SIZE*SIZE){ /*已经走完25步，则统计方案个数，打印方案，跳出递归*/
num++;
if (num<=3)/*打印前3种方案*/
printSolution();
}
else
for(dir=0;dir<=7;dir++){ /*依次试遍8个方向*/
u=x+row[dir]; /*得到的新坐标*/
v=y+col[dir];
if ((u>=0) && (u<=SIZE-1) && (v>=0) && (v<=SIZE-1) && (h[u][v]==0)){/*如果新坐标在棋盘上，并且这一格可以走*/
h[u][v]=i;/*占据位置[u,v]*/
try(u,v,i+1);
h[u][v]=0;
}
}
}
/*打印方案*/
void printSolution()
{
int row,col;
for(row=0;row<=SIZE-1;row++){
for(col=0;col<=SIZE-1;col++)
printf("%d\t",h[row][col]);
printf("\n");
}
printf("\n\n");
}
