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

JAY饭

步数是一样的，但是坐标不太一样。我按你的写法，除了移动顺序不同。
谢谢版主，这些题目都很有用

阿bang

1. # ! /urs/bin/env python
   
2. # coding=utf-8
   
3. # __author__ = 'bang'  CreateDate:2018/4/11
   
4. 
   
5. 
   
6. def findpath(startpoint, aimpoint):
   
7.     global stepcount
   
8.     global anserlist
   
9.     global FLAG
   
10.     FLAG += 1
    
11.     horsePos = startpoint  # 记录起始位置
    
12.     for i in stepTrace:
    
13.         if horsePos == i[-1]:
    
14.             stepcount = len(i) - 1
    
15.             break
    
16.     if stepcount > min(minsteplist) - 1:
    
17.             FLAG -= 1
    
18.             return
    
19.     for history in historyPos[:]:
    
20.         if horsePos == history[0]:
    
21.             if stepcount > history[1]:
    
22.                 FLAG -= 1
    
23.                 return  # 如果该点已经出现在历史记录的点中，且步数较高，则结束
    
24.             else:
    
25.                 historyPos.append((horsePos, stepcount))
    
26.                 historyPos.remove(history)
    
27.             break       # 刷新某个点的最优步数记录
    
28.     else:
    
29.         historyPos.append((horsePos, stepcount))        # 位置加入历史记录
    
30.     horseNextPos = [(horsePos[0] + rule[0], horsePos[1] + rule[1]) for rule in HORSERULE
    
31.                     if (horsePos[0] + rule[0], horsePos[1] + rule[1]) in CHESSBOARD]       # 生成下个一可能的点
    
32.     if aimpoint in horseNextPos:  # 如果目标点在下一个可能的点，则记录路径长度和路径结果
    
33.         for i in stepTrace:
    
34.             if i[-1] == horsePos and i not in anserlist:
    
35.                 anserlist.append(i)
    
36.                 minsteplist.append(len(i))
    
37.                 # break
    
38.         FLAG -= 1
    
39.         return
    
40.     else:
    
41.         # 记录轨迹
    
42.         for i in stepTrace[:]:
    
43.             temp = i[:]
    
44.             if horsePos == temp[-1]:
    
45.                 for point in horseNextPos:
    
46.                     temp.append(point)
    
47.                     stepTrace.append(temp[:])
    
48.                     temp.pop()
    
49.                 stepTrace.remove(temp)
    
50.                 break
    
51.     for point in horseNextPos:
    
52.         findpath(point, aimpoint)   # 遍历每个可能的点
    
53.     FLAG -= 1
    
54.     if FLAG == 0:               # 返回到最外层的函数才打印结果
    
55.         for i in anserlist:         # 输出达到终点的最短路径
    
56.             if len(i) == min(minsteplist):
    
57.                 # i.append(aimpoint)
    
58.                 print(i)
    
59.         print(minsteplist)
    
60.         print(len(historyPos))
    
61. 
    
62. 
    
63. 
    
64. 
    
65. CHESSBOARD = tuple((i, j) for i in range(9) for j in range(10))  # 初始化象棋盘
    
66. HORSERULE = tuple((i, j) for i in (-1, 1, 2, -2) for j in (-1, 1, 2, -2) if abs(i) + abs(j) == 3)  # 定义马的行棋规则
    
67. startPos = (0, 0)  # input("请输入马的初始位置(以英文逗号隔开)：")
    
68. historyPos = [(startPos, 0)]  # 记录马曾经经过的点，以及经过该点的步数
    
69. aimPos = (7, 7)  # input("请输入马的终点位置(以英文逗号隔开)：")
    
70. stepTrace = [[startPos]]  # 记录每次行走的路径
    
71. stepcount = 0      # 记录当前步数
    
72. # 判断最小步数，默认1000以内肯定能找到解
    
73. minsteplist = [1000]
    
74. anserlist = []
    
75. FLAG = 0
    
76. findpath(startPos, aimPos)

复制代码

写了个贼蠢的，貌似是先深度优先的递归，调来调去搞不明白了，总有差错，先发上来。
后来再开车的时候，想到一个开枝散叶的广度优先法，应该会改进和简洁不少。一会实现一下发出来。
等发完后，再学习各位大神的方法

阿bang

1. def findpath(startPt, endPt):
   
2.     horseTrace = [[startPt]]
   
3.     pointList = [startPt]
   
4.     answerlist = []
   
5.     endflag = 0
   
6.     while not endflag:
   
7.         lastSetpPtList = pointList[:]
   
8.         tempTrace = horseTrace[:]
   
9.         for i in tempTrace:
   
10.             startPt = i[-1]
    
11.             nextPt = [(startPt[0] + rulePt[0], startPt[1] + rulePt[1])
    
12.                       for rulePt in HORSERULE
    
13.                       if (startPt[0] + rulePt[0], startPt[1] + rulePt[1]) in CHESSROARD
    
14.                       ]
    
15.             for pt in nextPt:
    
16.                 if pt not in lastSetpPtList:
    
17.                     if pt not in pointList:
    
18.                         pointList.append(pt)
    
19.                     temp = i[:]
    
20.                     temp.append(pt)
    
21.                     horseTrace.append(temp[:])
    
22.                     temp.pop()
    
23.             horseTrace.remove(i)
    
24.             if endPt in nextPt:
    
25.                 for i in horseTrace:
    
26.                     if i[-1] == endPt:
    
27.                         horseTrace.remove(i)
    
28.                         answerlist.append(i)
    
29.                         endflag = 1
    
30.                         break
    
31.     return answerlist
    
32. 
    
33. 
    
34. CHESSROARD = tuple([(i, j) for i in range(9) for j in range(10)])
    
35. HORSERULE = tuple([(i, j) for i in [-1, -2, 1, 2] for j in [-1, -2, 1, 2] if abs(i) + abs(j) == 3])
    
36. startPt = (0, 0)
    
37. endPt = (5, 8)
    
38. for i in findpath(startPt, endPt):
    
39.     print(i)
    
40. print(len(findpath(startPt, endPt)))

复制代码

重写了一个开枝散叶法。。。这个就颇为满意了。

阿bang

初步总结一下，如果是求最优解（假设最短路径为n），那么一般采用需要用广度优先，遍历每个节点，效率高。这样可以进行第n次探索的时候，即找到最优解，且可以找出所有的最优解。
如果只是求解的话，当数据量很大的时候（每一级的节点很多的时候），广度优先虽然可以求得最优解，但是时间是指数级增长的。
因此用深度优先法求出其中一个解，效率可能会高一些。

以后再研究研究。

众生

请问
if 0<=p2[0]<m and 0<=p2[1]<n and chess[p2[0]][p2[1]] == 0 and p2 not in rightway:
这里的【p2 not in rightway】这个判断会不会与chess[p2[0]][p2[1]] == 0重复了呀，都是判断走没走过的