马踏棋盘（关于回溯法的应用）

问题描述：

在中国象棋中，棋子马的走法是走“日”字型；

现有一8*8的中国象棋棋盘，棋子马从任意给定一点出发，走“日”字型，要求为马

寻找一条走遍棋盘每一格并且只经过一次的一条路径。

给定一个初始的坐标，如（0,0），从该点向外走“日”字型,有两种走法，若起始点

在（4,4），棋子的每个方向都可以走，有八种走法。

所以正常计算的计算量过大，使用回溯法会优化不少

回溯算法的基本思想是：

        回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续

下一条路。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二

步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位

置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯算法说白了

就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状

态）的节点，从而减少状态空间树节点的生成。

1. 
   
2. #include <stdio.h>
3. #include <conio.h>
4. #define N 8
5. 
   
6. 
   
7. struct nx//实时移动到的位置坐标
8. {
9. int m;
10. int n;
11. };
12. 
    
13. 
    
14. int array[9][9];
15. int count;//生成结果数
16. 
    
17. 
    
18. void Initialization()//初始化函数
19. {
20. int line;
21. int row;
22. 
    
23. 
    
24. for (line = 1; line <= 8; line++)
25. {
26. for (row = 1; row <= 8; row++)
27. {
28. array[line][row] = 0;//先对行列都赋值为0，表示没有走过
29.   //每当马走过一个点，赋值为1
30. }
31. }
32. }
33. 
    
34. 
    
35. struct nx move_house(int direct, int x, int y) //马从位置（x,y）出发，从各个方向开始尝试
36. {
37. struct nx next;
38. switch (direct)
39. {
40. case 0: next.m = x + 1; next.n = y + 2; break;
41. case 1: next.m = x + 2; next.n = y + 1; break;
42. case 2: next.m = x + 2; next.n = y - 1; break;
43. case 3: next.m = x + 1; next.n = y - 2; break;
44. case 4: next.m = x - 1; next.n = y - 2; break;
45. case 5: next.m = x - 2; next.n = y - 1; break;
46. case 6: next.m = x - 2; next.n = y + 1; break;
47. case 7: next.m = x - 1; next.n = y + 2; break;
48. }
49. return next;//将位置坐标的及结构体返回
50. }
51. 
    
52. 
    
53. int Illegal_put(int deepth, int m, int n)
54. {
55. if (n > N || m > N || n < 1 || m < 1 || array[m][n] != 0)
56. return 0;//当棋子超出棋盘范围时候，或该点已经走过，对这个位置赋值0
57. else
58. return 1;
59. }
60. 
    
61. 
    
62. void List_output()
63. {
64. int line;
65. int row;
66. printf("第[%d]种走法\n", count+1);
67. for (line = 1; line <= N; line++)
68. {
69. for (row = 1; row <= N; row++)
70. {
71. printf("%3d", array[line][row]);
72. }
73. printf("\n");
74. }
75. printf("\n");
76. }
77. 
    
78. 
    
79. void house_track(int deepth, int x,int y)
80. {
81. int direct;
82. struct nx next;
83. if (deepth <= N*N)
84. {
85. for (direct = 0; direct <= 7; direct++)
86. {
87. next = move_house(direct, x, y);
88. if (Illegal_put(deepth, next.m, next.n))
89. {
90. array[next.m][next.n] = deepth;
91. house_track(deepth + 1, next.m, next.n);
92. }
93. }
94. if (direct == 8)
95. array[x][y] = 0;
96. }
97. else
98. {
99. List_output();
100. array[x][y] = 0;
101. count++;
102. }
103. }
104. 
     
105. 
     
106. 
     
107. int main()
108. {
109. int start_x;
110. int start_y;//棋子开始的坐标
111. Initialization();//对棋盘初始化
112. printf("输出棋子马的初始坐标(x,y):");
113. scanf("%d%d", &start_x, &start_y);
114. array[start_x][start_y] = 1;
115. count = 0;
116. house_track(2, start_x, start_y);
117. _getch();
118. printf("一共有%d种可能\n", count);
119. }