马踏棋盘问题，小甲鱼答案有一部分没看明白

WwangHB

马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。
国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马走日”的规则将“马”进行移动，要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。

1. #include <stdio.h>
   
2. 
   
3. #define X 8
   
4. #define Y 8
   
5. 
   
6. int chess[X][Y];
   
7. 
   
8. // 找到下一个可走的位置
   
9. int next(int *px, int *py, int count)
   
10. {
    
11.         int x = *px;
    
12.         int y = *py;
    
13. 
    
14.         switch(count)
    
15.         {
    
16.         case 0:
    
17.                 if (x+2<=X-1 && y-1>=0 && chess[x+2][y-1] == 0)
    
18.                 {
    
19.                         *px = x + 2;
    
20.                         *py = y - 1;
    
21.                         return 1;
    
22.                 }
    
23.                 break;
    
24.         case 1:
    
25.                 if (x+2<=X-1 && y+1<=Y-1 && chess[x+2][y+1] == 0)
    
26.                 {
    
27.                         *px = x + 2;
    
28.                         *py = y + 1;
    
29.                         return 1;
    
30.                 }
    
31.                 break;
    
32.         case 2:
    
33.                 if (x+1<=X-1 && y-2>=0 && chess[x+1][y-2] == 0)
    
34.                 {
    
35.                         *px = x + 1;
    
36.                         *py = y - 2;
    
37.                         return 1;
    
38.                 }
    
39.                 break;
    
40.         case 3:
    
41.                 if (x+1<=X-1 && y+2<=Y-1 && chess[x+1][y+2] == 0)
    
42.                 {
    
43.                         *px = x + 1;
    
44.                         *py = y + 2;
    
45.                         return 1;
    
46.                 }
    
47.                 break;
    
48.         case 4:
    
49.                 if (x-2>=0 && y-1>=0 && chess[x-2][y-1] == 0)
    
50.                 {
    
51.                         *px = x - 2;
    
52.                         *py = y - 1;
    
53.                         return 1;
    
54.                 }
    
55.                 break;
    
56.         case 5:
    
57.                 if (x-2>=0 && y+1<=Y-1 && chess[x-2][y+1] == 0)
    
58.                 {
    
59.                         *px = x - 2;
    
60.                         *py = y + 1;
    
61.                         return 1;
    
62.                 }
    
63.                 break;
    
64.         case 6:
    
65.                 if (x-1>=0 && y-2>=0 && chess[x-1][y-2] == 0)
    
66.                 {
    
67.                         *px = x - 1;
    
68.                         *py = y - 2;
    
69.                         return 1;
    
70.                 }
    
71.                 break;
    
72.         case 7:
    
73.                 if (x-1>=0 && y+2<=Y-1 && chess[x-1][y+2] == 0)
    
74.                 {
    
75.                         *px = x - 1;
    
76.                         *py = y + 2;
    
77.                         return 1;
    
78.                 }
    
79.                 break;
    
80.         }
    
81. 
    
82.         return 0;
    
83. }
    
84. 
    
85. int setHorse(int x, int y, int tag)
    
86. {
    
87.         int x1 = x, y1 = y, flag = 0, count = 0;
    
88. 
    
89.         // tag记录轨迹
    
90.         chess[x][y] = tag;
    
91.         // 如果tag等于64退出程序
    
92.         if (tag == X*Y)
    
93.         {
    
94.                 return 1;
    
95.         }
    
96. 
    
97.         // 如果可以走，那么flag为1
    
98.         flag = next(&x1, &y1, count);
    
99.         // 否则尝试其他路径
    
100.         while (flag == 0 && count < 7)
     
101.         {
     
102.                 count += 1;
     
103.                 flag = next(&x1, &y1, count);
     
104.         }
     
105. 
     
106.         // 递归进入下一个坐标
     
107.         while (flag)
     
108.         {
     
109.                 // 返回1表示成功找到落脚点
     
110.                 if (setHorse(x1, y1, tag+1))
     
111.                 {
     
112.                         return 1;
     
113.                 }
     
114.                 // 否则从上一步重新尝试
     
115.                 x1 = x;
     
116.                 y1 = y;
     
117.                 count += 1;
     
118.                 flag = next(&x1, &y1, count);
     
119.                 while (flag == 0 && count < 7)
     
120.                 {
     
121.                         count += 1;
     
122.                         flag = next(&x1, &y1, count);
     
123.                 }
     
124.         }
     
125. 
     
126.         if (flag == 0)
     
127.         {
     
128.                 chess[x][y] = 0;
     
129.         }
     
130. 
     
131.         return 0;
     
132. }
     
133. 
     
134. int main(void)
     
135. {
     
136.         int i, j;
     
137. 
     
138.         for (i = 0; i < X; i++)
     
139.         {
     
140.                 for (j = 0; j < Y; j++)
     
141.                 {
     
142.                         chess[i][j] = 0;
     
143.                 }
     
144.         }
     
145. 
     
146.         // 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
     
147.         // 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
     
148.         if (setHorse(2, 0, 1))
     
149.         {
     
150.                 for (i = 0; i < X; i++)
     
151.                 {
     
152.                         for (j = 0; j < Y; j++)
     
153.                         {
     
154.                                 printf("%02d  ", chess[i][j]);
     
155.                         }
     
156.                         putchar('\n');
     
157.                 }
     
158.         }
     
159.         else
     
160.         {
     
161.                 printf("可惜无解！\n");
     
162.         }
     
163. 
     
164.         return 0;
     
165. }

复制代码

在setHOrse函数中while(flag) 迭代如果flag不为0则得到解，如果flag为0则退出循环，应该是无解，函数返回0，为什么中间要有一个

1.         if (flag == 0)
   
2.         {
   
3.                 chess[x][y] = 0;
   
4.         }

复制代码

并且当我删掉这段的时候，代码多次运行结果都为 无解？ 这段代码的作用是什么

永恒的蓝色梦想

领鱼币

xiaosi4081

领鱼币x2

lijiachen

正好缺鱼币

赚小钱

马走过的地方会被设置为1(二维数组上)，flag 表示能否找到，下一个位置，如果 flag 表示，在当前位置没有一个可以走的下一个位置，那么应该回退，此时，即表示当前的路是错的，所以应该在二维数组将当前位置设置为0

PS: 算法属于回溯算法。
回溯算法的核心思想是:
选择一个起点出发，沿着某一条路，不断检测是否可用，
如果可用就继续这条路(即深度遍历)
当遇到某种情况，可以确定，这条路行不通的时候，(剪枝函数)
就回头(回溯)，

quark

帮顶。。。