国际象棋马走日（骑士周游）

 1 /*
 2 **假设国际象棋棋盘有5*5=25个格子，设计一个程序，使棋子从初始位置开始跳马，能够把棋盘格子全部走一遍
 3 **每个格子只允许走一次。
 4 **要求：1)写出其中一个解。
 5         2)求总共有多少个解。
 6 **/
 7 
 8 //算法思路：
 9 /*
10 **由于对于程序来讲，每一个格子都是新的开始，都面临着同样的选择，即都有八个方向的选择
11 **因此适用于递归思想。至于能否走通，得去尝试。递归过程中，产生一颗递归树，检查过程中
12 **走不通就剪枝。尝试下一个树枝。因此有int trial(int x,int y)函数。棋盘用一个二维数组
13 **表示棋子序号，一个坐标代表，再用一个二维数组记录棋盘的某个坐标是否已经被踏过。
14 */
15 
16 #include<stdio.h>
17 
18 int trace[25] = {0}, counter = 0;
19 int steps = 0, k = 1;             //k在此的作用为只打印一种方案的开关
20 int chessboard[5][5];            //棋盘
21 int flag[5][5];                    //给棋盘做标记
22 
23 //函数声明区
24 void init();
25 void printResult(int k);
26 void walk(int x, int y);
27 
28 int main(){
29     init();
30     walk(0, 0);
31     printf("the answer number:%d
", counter);
32     return 0;
33 }
34 
35 /*
36 **探寻可走的路
37 */
38 void walk(int x, int y)
39 {
40     if(x<0 || x >4 || y<0 || y > 4 || flag[x][y] == 1)
41         return;                            //走不通，返回.
42     flag[x][y] = 1;
43     trace[steps++] = chessboard[x][y];    //记录每一步所走的位置
44     if(steps > 24)
45     {
46         counter++;            
47         printResult(100);
48         flag[x][y] = 0;
49         steps--;
50         return;
51     }
52     //这里是每个格子的各种走法
53     walk(x + 1, y + 2);        //上走有拐
54     walk(x + 1, y - 2);        //上走左拐
55     walk(x - 1, y + 2);        //下走有拐
56     walk(x - 1, y - 2);        //下走左拐
57     walk(x + 2, y + 1);        //右走上拐
58     walk(x + 2, y - 1);        //右走下拐
59     walk(x - 2, y + 1);        //左走上拐
60     walk(x - 2, y - 1);        //左走下拐
61     flag[x][y] = 0;
62     steps--;
63 }
64 
65 
66 //初始化二维数组
67 void init()
68 {
69     int i,j,pos = 1;
70     for(i = 0 ; i < 5 ; i++)
71         for(j = 0 ; j < 5 ; j++)
72         {
73             chessboard[i][j] = pos++;     //初始化棋盘
74             flag[i][j] = 0;                //初始化话标记
75         }
76 }
77 
78 
79 /*
80 **打印第k个结果,k为0默认打印全部。
81 */
82 
83 void printResult(int k)
84 {
85     int i;
86     static num = 0;
87     if(k !=0 )
88         if(++num != k)
89             return;
90     printf("The %dth case is: for example [step,point]
",k);
91     for (i = 0; i < 25; i++)
92     {
93         printf("[%-2d,%-2d] ", i+1, trace[i]);
94         if((i+1)%5==0)
95             printf("
");
96     }
97 }