python小练习（012）：象棋中“马”的日字形走法研究

jerryxjr1220

python小练习（010）和（011）的解答，下周公布（周末回家了没带电脑 ）

周末我们就研究一下象棋中“马”的日字形走法吧。

我们知道“马”只能“日”字形行走（横向“日”字形也可）。

假设我有一个8x8的国际象棋棋盘，在棋盘的左下角（0,0）的位置有一个“马”，那么如果只走1步的话，这个“马”可能出现的位置是（1,2），（2,1）。

现在的问题是这个“马”应该怎么走才能到对角（7,7）呢？

==========
|              1    1 |
|                       |
|           1    1    |
|                       |
|         1            |
|                       |
|       1              |
| 1                    |
==========
输出结果像这样：

1. Done!
   
2. (0, 0)
   
3. (2, 1)
   
4. (3, 3)
   
5. (4, 5)
   
6. (5, 7)
   
7. (6, 5)
   
8. (7, 7)
   
9. [Finished in 0.2s]

复制代码

那么用python怎么实现呢？大家来动脑筋吧！

jerryxjr1220

其实，起点和终点可以任意设定，这是设计简单的象棋AI中必不可少的环节。

jerryxjr1220

大家有没有想出解法呢？
我还是用的探索法，探索法解这类不确定路径问题还是非常有优势的。

1. #初始化
   
2. m=8
   
3. n=8
   
4. chess = [[0]*m for i in range(n)]
   
5. #定义“马”的跳法
   
6. move = [(-1,2),(-1,-2),(1,2),(1,-2),(-2,1),(-2,-1),(2,1),(2,-1)]
   
7. #定义起点和终点
   
8. start = (0,0)
   
9. end = (7,7)
   
10. #初始化最优路径
    
11. rightway = {}
    
12. #初始化探索列表（从终点开始）
    
13. trylist = [end]
    
14. #第一次探索开始
    
15. p1 = trylist.pop(0)
    
16. 主程序循环
    
17. while p1 != start:
    
18.         for d in move:
    
19.                 p2 = (p1[0] + d[0] , p1[1] + d[1])
    
20.                 if 0<=p2[0]<m and 0<=p2[1]<n and chess[p2[0]][p2[1]] == 0 and p2 not in rightway:
    
21.                         chess[p2[0]][p2[1]] = 1
    
22.                         trylist.append(p2)
    
23.                         rightway[p2] = p1
    
24.         try:
    
25.                 p1 = trylist.pop(0)
    
26.         except:
    
27.                 print ('No solution!')
    
28. else:
    
29. #到达起点后，从起点开始回溯整个路径
    
30.         print ('Done!')
    
31.         print (start)
    
32.         p = start
    
33.         while p != end:
    
34.                 p = rightway[p]
    
35.                 print (p)

复制代码

jerryxjr1220

另外来看一个探索法解迷宫问题的例子，也是我用探索研究迷宫问题时候写的。

                               
登录/注册后可看大图

                               
登录/注册后可看大图

jerryxjr1220

可以看到整个思路非常相近。
更新完毕。

Jonin616

自己写了一个算法 但算不出最优，只能计算出需要50步走到（7，7），还在思考中......................

Jonin616

接上楼，按自己的思路写了回溯，最优步数从50步下降到了37步，但到了37步程序就动不了了，迟迟没有进一步显示更优的步数，而且程序用时很长，从实用性角度说肯定是不合格的

jerryxjr1220

Jonin616 发表于 2017-2-6 17:02
接上楼，按自己的思路写了回溯，最优步数从50步下降到了37步，但到了37步程序就动不了了{:10_269 ...

说说看你的思路，可以探讨探讨如何优化

jerryxjr1220

Jonin616 发表于 2017-2-6 17:02
接上楼，按自己的思路写了回溯，最优步数从50步下降到了37步，但到了37步程序就动不了了{:10_269 ...

明天我准备分享一个用python写的“马踏棋盘”的程序，就是一个“马”如何一次性遍历整个棋盘，不能重复走。

用的方法同样是“回溯法”（又叫“深度优先搜索”算法）。

同样的程序用C语言写可能要上百行，用python写大概30多行代码就够了

Jonin616

jerryxjr1220 发表于 2017-2-6 17:17
说说看你的思路，可以探讨探讨如何优化

主要是运用三个列表
列表 step 记录所走过的路径（也就是经过的每个坐标）
列表 direction_count 记录路径上每个坐标曾经经过的方向（一共8个方向），用每个方向用数字0~7表示，这样就可以通过下标可以遍历到direction_choise中的8个方向参数
列表direction_choise记录八个可能的方向参数，例如[(1,2),(-1,2)..........]这样，这一点跟您的想法一样

最后还有一个列表记录当前坐标位置

每当前进时，按顺序遍历direction_choise中的参数，将当前坐标与direction_choise中的参数相加，并进行边界判断，如果通过了边界判断，那就在step中加入新的坐标，同时将direct_count中对应的位置的数值加上1，这样一旦进行回溯时，就可以通过direction_count中的数值判断在这个坐标上曾经走过的方向是哪几个

每当一个坐标上对应的direction_count参数等于8，或者step路径到达（7，7）时，就进行回溯操作

不知这样写老师能不能理解，初学者还请见谅

Jonin616

jerryxjr1220 发表于 2017-2-6 17:17
说说看你的思路，可以探讨探讨如何优化

我没有看老师在上面贴出的代码，不懂我的思路跟老师的一不一样

Jonin616

1. def horsejump():
   
2.     dir_choise = [(-1,2),(-1,-2),(1,2),(1,-2),(-2,1),(-2,-1),(2,1),(2,-1)]
   
3.     dir_count = []
   
4.     for i in range(0,60):
   
5.         dir_count.append(0)
   
6. 
   
7.     bestway = []
   
8.     step = []
   
9.     count_step = 0
   
10.     horse_locate = [0,0]
    
11.     dest_locate = [7,7]
    
12.     step.append(horse_locate.copy())
    
13. 
    
14.     finish = 0
    
15.     back_flag = 0
    
16. 
    
17.     while finish == 0:
    
18.         while back_flag == 0:
    
19.             if horse_locate == dest_locate:
    
20.                 break
    
21.                
    
22.             if count_step != 0 and dir_count[count_step] == 8:
    
23. 
    
24.                 back_flag = 1
    
25.                 break
    
26.             #print(step)   
    
27.             if horse_locate != dest_locate and ((0 <= horse_locate[0] + dir_choise[dir_count[count_step]][0] <= 7) and (0 <= horse_locate[1] + dir_choise[dir_count[count_step]][1] <= 7)):
    
28.                 if ([horse_locate[0] + dir_choise[dir_count[count_step]][0] ,horse_locate[1] + dir_choise[dir_count[count_step]][1]] in step):
    
29.                     dir_count[count_step] += 1
    
30.                     continue
    
31.                 else:
    
32.                     horse_locate[0] += dir_choise[dir_count[count_step]][0]
    
33.                     horse_locate[1] += dir_choise[dir_count[count_step]][1]
    
34.                     dir_count[count_step] += 1
    
35.                     count_step += 1
    
36.                     step.append(horse_locate.copy())
    
37.                     
    
38.             if horse_locate != dest_locate and (horse_locate[0] + dir_choise[dir_count[count_step]][0] < 0 or horse_locate[0] + dir_choise[dir_count[count_step]][0] > 7 or horse_locate[1] + dir_choise[dir_count[count_step]][1] < 0 or horse_locate[1] + dir_choise[dir_count[count_step]][1] > 7):
    
39.                 dir_count[count_step] += 1
    
40.                 continue
    
41.         if back_flag == 1:
    
42.             dir_count[count_step] = 0
    
43.             count_step -= 1
    
44.             step.remove(horse_locate.copy())
    
45.             horse_locate = step[count_step].copy()
    
46.             back_flag = 0
    
47.         
    
48.         if horse_locate == dest_locate:
    
49.             back_flag = 1
    
50.             if len(bestway) == 0:
    
51.                 for i in step:
    
52.                     bestway.append(i.copy())
    
53.             if len(step) < len(bestway):
    
54.                 #这里用print函数测试下输出结果
    
55.                 print('输出目前的最优路径长度：',len(step))
    
56.                 bestway.clear()
    
57.                 for i in step:
    
58.                     bestway.append(i.copy())
    
59.         if dir_count[0] == 8:
    
60.             finish = 1
    
61.             print(bestway)
    
62.             

复制代码

Jonin616

上面的代码就是刚才写的 还有错误 只能输出到步数37，然后就动不了了
脑子已炸

jerryxjr1220

Jonin616 发表于 2017-2-6 18:15
上面的代码就是刚才写的 还有错误 只能输出到步数37，然后就动不了了
脑子已炸{:10_2 ...

你的程序我没有细看，不过从你的思路的描述来看，我基本上理解你的意思。
你的问题出在你用的方法错了，回溯法（“深度优先搜索”算法）对于这题是很难求得最优解的，只能得到一组可行解（就是你的50步或者37步的那个解），如果要求最优解或者近似最优解，需要用探索法（“广度优先搜索”算法），这2种方法正好是互补的关系，具体定义你可以网上搜一下，你也可以参考我的淘贴“python小练习”正好讲到这部分内容。
回溯法正好是“马踏棋盘”的解法，明天你可以看下我贴的代码。回溯法能求解的题目很多，比如解迷宫（当然迷宫也可以用探索法求解），解数独，解八皇后问题等等。但是不适合解最优化问题。

PS：我不是老师，我也是跟着小甲鱼老师的视频自学了4个月的python而已。一起研究，共同进步。

Jonin616

jerryxjr1220 发表于 2017-2-6 19:12
你的程序我没有细看，不过从你的思路的描述来看，我基本上理解你的意思。
你的问题出在你用的方法错了 ...

你怎么明白回溯和探索的区别 网上的定义太抽象了 可以简单说说吗

jerryxjr1220

Jonin616 发表于 2017-2-6 21:13
你怎么明白回溯和探索的区别 网上的定义太抽象了 可以简单说说吗

回溯法（“深度优先搜索”）和探索法（“广度优先搜索”）的区别：
举个例子，如果我要从上述的这个表中搜索出“C4”（炸弹）的话，我们用回溯法和探索法看看究竟有什么区别。
如果用回溯法的话，它的搜索顺序是这样的：
A1 - A2 - A3 - A4（回溯） - B1 - B2 - B3 - B5（回溯） - B4 - B6（回溯） - C1 - C2 - C4 （找到！） 终止搜索

如果用探索法的话，它的搜索顺序是这样的：（A1，B1，C1在初始化时已经放入候选列表待检）
A1 （A2加入候选列表）- B1（B2加入候选列表） - C1（C2、C3加入候选列表） - A2（A3加入候选列表） - B2（B3、B4加入候选列表） - C2（C4加入候选列表） - C3（C5加入候选列表） - A3（A4加入候选列表） - B3（B5加入候选列表） - B4（B6加入候选列表） - C4（找到！）终止搜索

看出两者的区别了么？
深度优先搜索，顾名思义就是纵向的一条一条路径开始走到底，走不通，掉头回溯，再走另外一条分支。
广度优先搜索，就是按照从上到下的节点，依次遍历所有节点，把与父节点相连的所有子节点加入候选列表依次访问。

所以，如果回到马从（0，0）跳到（7，7）的问题，用回溯法的话，它是一条道走到黑，需要跳50步才能跳到（7，7）。而如果是用探索法的话，第一次探索的是与（0，0）相连的所以节点，第二次探索的是与前面所有节点相连的所有节点。。。所以可以看出，用探索法的话，很快就能找到目标节点。

Jonin616

jerryxjr1220 发表于 2017-2-6 22:17
回溯法（“深度优先搜索”）和探索法（“广度优先搜索”）的区别：
举个例子，如果我要从上述的这个 ...

好的 谢谢 我再用广度优先写一个看看

JAY饭

思路非常新颖。受教了。
对了，我觉得这里应该是 if 0<=p2[0]< n，而不是 if 0<=p2[0]< m, 反复想了几次，感觉还是这样。
因为P2[0]是大列表里面的小列表位置，而大列表里面的小列表一开始是按照n来分配的，所以它应该是
小于n,一旦列表长宽不一致会有影响。感觉可能会提示out index

JAY饭

上面是上面回复的图

这个求得是近似最优解吧。而且跟移动列表的的排列顺序有关，
我的答案是这个

jerryxjr1220

JAY饭 发表于 2018-1-23 15:32
上面是上面回复的图

这个求得是近似最优解吧。而且跟移动列表的的排列顺序有关，

其实是一样的，你没有算起始点（0,0）