用Python玩烧脑小游戏《一笔画完》，瞬间闯到100关

2023-02-26

path 顶点 used

昨天和朋友出去外面吃饭，吃完饭后朋友打开了一个小程序玩了起来......游戏长这样大概玩法是：从地图中猫的位置开始出发，并且经过所有的格子就算过关。游戏还算挺有意思的，经过我的不断努力终于过到了30来关的样子。并且随着游戏关卡的增加，游戏难度也变得越来越大，过一关需要非常久的时间。最近也正好在研究算

昨天和朋友出去外面吃饭，吃完饭后朋友打开了一个小程序玩了起来......

游戏长这样

大概玩法是：从地图中猫的位置开始出发，并且经过所有的格子就算过关。游戏还算挺有意思的，经过我的不断努力终于过到了 30 来关的样子。

并且随着游戏关卡的增加，游戏难度也变得越来越大，过一关需要非常久的时间。

最近也正好在研究算法，就打算看能不能写个通用的算法来找出每个地图的解。

哥尼斯堡的"七桥问题"

这个游戏的玩法和哥尼斯堡的"七桥问题"有点类似。

哥尼斯堡的"七桥问题"：18 世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如下图)。是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?

当时人们想到的证明方法是把七座桥的走法都列出来一个一个试验，用排列组合的知识很容易得到七座桥所有的走法大概有 7! = 5040 种，如果真的逐一试验，会是个很大的工作量。

但数学家欧拉没有这样想，欧拉把两座岛和河两岸抽象成顶点，七座桥抽象成连接每个顶点的七条边，那么这个问题就能被抽象成下面的图：

假设每座桥都恰好走过一次，那么对于 A、B、C、D 四个顶点中的每一个顶点，需要从某条边进入，同时从另一条边离开，进入和离开顶点的次数是相同的，即每个顶点有多少条进入的边，就有多少条出去的边。

也就是说：每个顶点相连的边是成对出现的，即每个顶点的相连边的数量必须是偶数。

很明显，上图中 A、C、D 三个顶点相连的边都有 3 条，B 顶点的相连边为 5 条，都是奇数。因此这个图无法从一个顶点出发，且恰好走过每座桥一次。

由此次证明，人们又得到了欧拉路关系，要使得一个图形可以一笔画完，必须满足如下两个条件：

图形必须是连通的不能有孤立的点。
图中拥有奇数连接边的点必须是 0 或 2。

对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。那么这个游戏是不是就是让我们找到一条欧拉路呢?

对游戏进行抽象

按照上面证明七桥问题的方法，我们可以将游戏的地图抽象成这样：

其中 14 号顶点为起点。
顶点和边的关系在程序中可以刻画成一个二维列表。

graph = [ 
    [1, 6],    #0 
    [0, 2],    #1 
    [1, 7, 3], #2 
    ... 
    [24, 19]   #25 
] 
1.
2.
3.
4.
5.
6.
7.

graph 列表的***层表示每一个顶点，第二层则是与当前顶点有边的顶点。

抽象完这张游戏地图后可以很清楚知道，这游戏并不是让我们找到一条欧拉路。

因为找到一条欧拉路，需要的是经过每一座桥，且只经过一次，也就是说每个顶点可以被多次经过。

而这个游戏需要的是经过每一个顶点，并不要求走完每一座桥，且顶点只能被经过一次。

哈密顿通路

在研究了七桥问题发现并不能解决这类问题后，我开始向团队的表哥们请教，其中一个表哥告诉我此类问题叫做哈密顿图 (这里感谢下团队的**@xq17**表哥)。

这里说的哈密顿图，实际上是哈密顿通路的一种特殊情况，指的是：由指定的起点出发，途中经过所有其他顶点且只经过一次，***返回起点，称之为哈密顿回路。如果给定的图 G 具有哈密顿回路，则称图 G 为哈密顿图。

那么现在目标明确了，这个游戏的解法就是找到某个给定图的哈密顿通路。

但是问题来了！！！哈密顿通路问题，在上世纪七十年代初，被证明是 NP-hard 问题：

一个复杂问题如果能在多项式时间内解决，那么它便被称为 P 类问题。
一个复杂问题如果不能确定在多项式时间内解决，那么它便被称为 NP 类问题。

什么意思呢？就拿质因数分解来说吧：

P 类问题：23x37=?
NP 类问题：已知 axb=740914799，且 a 和 b 都是质数，求 a 和 b 的值

让我们来看看这个问题有多复杂：

因为 axb=740914799，且 a 和 b 都是质数
设 P={x|2<=x<740914799/2，x 是质数}
易得 (a，b)∈PxP，即 P 与它自身的笛卡尔积

我们用一种叫做筛法的算法来求一下 P 集合的元素个数：

#! /usr/bin/env python 
# -*- coding: utf-8 -*- 
# Coding with love by Naiquan. 
import math 
import time 
start = time.clock() 
number = int(740914799/2) 
marks_list = [True] * (number + 1) 
marks_list[0] = marks_list[1] = False 
for i in range(2, int(math.sqrt(number)) + 1): 
    j = i 
    t = j 
    # 去掉倍数 
    while j * t <= number: 
        marks_list[j * t] = False 
        t += 1 
elapsed = str(time.clock() - start) 
print marks_list.count(True) 
print "Time used:" + elapsed 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

一共有 19841519 个质数，算了我大概 14 分钟。

PxP 的元素个数一共有 19841519^2 个，要一个个验证是否等于 740914799，无疑又是一项很大的工程，这就是典型的 NP 类问题。NP 类问题虽然难，但是可以很快验证一个给定的答案，是否正确。

比如上面的题，我告诉你答案 a=22229，b=33331，你很快就能验证答案是否正确了。而 NP-hard 问题则是比 NP 问题更难的问题，例如：围棋。

也就是说并不能找到一个友好的算法，来解决哈密顿通路问题。

算法设计

虽然找到一个图的哈密顿通路是 NP 困难的，但是好在游戏中的顶点不算太多，还是可以使用暴力一点的方法实现的，例如：图的深度优先遍历法(DFS) 即递归和回溯法思想。

算法流程：

①将当前顶点压入已访问栈和路径栈中。

②将与当前顶点相通的顶点列出来。

③随机选取一个相通的顶点，并判断此顶点是否在已访问栈中：

在已访问栈中则取另一个相通的顶点。
不在则将这个相通的顶点作为当前顶点。
若所有相通的顶点都在已访问栈中，则判断路径栈是否包含所有顶点。
路径栈中包含所有顶点，则路径栈为当前图的哈密顿通路。
不包含所有顶点则回到父顶点，并从已访问栈和路径栈中删除。

④反复执行 1~3。

算法实现

上面说过图的顶点和边的关系可以用一个二维列表来描述：

graph = [ 
    [1, 6],    #0 
    [0, 2],    #1 
    [1, 7, 3], #2 
    ... 
    [24, 19]   #25 
] 
1.
2.
3.
4.
5.
6.
7.

但是要手动输入这些顶点和边的关系还是太麻烦了。仔细想了下，如果每个顶点的上下左右有顶点，就一定与上下左右的顶点有边。

那么这个二维列表就可以简化成

graph = [ 
    [1,1,1,1,1,1], 
    [1,0,1,1,0,1], 
    [1,1,1,1,1,1], 
    [1,0,1,1,0,1], 
    [1,1,1,1,1,1], 
    [0,0,0,0,0,0]    #每个1代表一个顶点 1与上下左右的1都有边 与0则没有 长宽相等易于编写代码 
] 
1.
2.
3.
4.
5.
6.
7.
8.

还可以再简化成一维列表：

graph = [ 
    '111111', 
    '101101', 
    '111111', 
    '101101', 
    '111111', 
    '000000' 
] 
1.
2.
3.
4.
5.
6.
7.
8.

简直机智如我啊！于是我写了个函数对一维列表进行转换：

def get_index(i, j, G): 
    num = 0 
    for a in xrange(i): 
        num += G[a].count('0') 
    for b in xrange(j): 
        if G[i][b] == '0': 
            num += 1 
    return i * len(G) + j - num 
def get_graph(G): 
    G = [list(x) for x in G] 
    EG = [] 
    for i in xrange(len(G)): 
        for j in range(len(G[i])): 
            if G[i][j] == '0': 
                continue 
            side_list = [] 
            if j+1 <= len(G[i]) - 1: 
                if G[i][j+1] == '1': 
                    index = get_index(i, j+1, G) 
                    side_list.append(index) 
            if j-1 >= 0: 
                if G[i][j-1] == '1': 
                    index = get_index(i, j-1, G) 
                    side_list.append(index) 
            if i+1 <= len(G) - 1: 
                if G[i+1][j] == '1': 
                    index = get_index(i+1, j, G) 
                    side_list.append(index) 
            if i-1 >= 0: 
                if G[i-1][j] == '1': 
                    index = get_index(i-1, j, G) 
                    side_list.append(index) 
            EG.append(side_list) 
    return EG 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.

而算法的实现用图的邻接矩阵则更为方便，因此我写了一个将上列二位列表转换成邻接矩阵形式的函数：

def get_matrix(graph): 
    result = [[0]*len(graph) for _ in xrange(len(graph))]  # 初始化 
    for i in xrange(len(graph)): 
        for j in graph[i]: 
            result[i][j] = 1  # 有边则为1 
    return result 
1.
2.
3.
4.
5.
6.

主要的 DFS 算法如下：

# graph为图的邻接矩阵 used为已访问栈 path为路径栈 step为已经遍历的顶点的个数 
def dfs(graph, path, used, step): 
    if step == len(graph): # 判断顶点是否被遍历完毕 
        print path 
        return True 
    else: 
        for i in xrange(len(graph)): 
            if not used[i] and graph[path[step-1]][i] == 1: 
                used[i] = True 
                path[step] = i 
                if dfs(graph, path, used, step+1): 
                    return True 
                else: 
                    used[i] = False  # 回溯 返回父节点 
                    path[step] = -1 
    return False 
def main(graph, v): 
    used = []  # 已访问栈 
    path = []  # 路径栈 
    for i in xrange(len(graph)): 
        used.append(False)  # 初始化 所有顶点均未被遍历 
        path.append(-1)     # 初始化 未选中起点及到达任何顶点 
    used[v] = True          # 表示从起点开始遍历 
    path[0] = v             # 表示哈密顿通路的***个顶点为起点 
    dfs(graph, path, used, 1) 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

完整代码如下：

#! /usr/bin/env python 
# -*- coding: utf-8 -*- 
# Coding with love by Naiquan. 
def dfs(graph, path, used, step): 
    if step == len(graph): 
        print path 
        return True 
    else: 
        for i in xrange(len(graph)): 
            if not used[i] and graph[path[step-1]][i] == 1: 
                used[i] = True 
                path[step] = i 
                if dfs(graph, path, used, step+1): 
                    return True 
                else: 
                    used[i] = False 
                    path[step] = -1 
    return False 
def main(graph, v): 
    used = [] 
    path = [] 
    for i in xrange(len(graph)): 
        used.append(False) 
        path.append(-1) 
    used[v] = True 
    path[0] = v 
    dfs(graph, path, used, 1) 
def get_index(i, j, G): 
    num = 0 
    for a in xrange(i): 
        num += G[a].count('0') 
    for b in xrange(j): 
        if G[i][b] == '0': 
            num += 1 
    return i * len(G) + j - num 
def get_graph(G): 
    G = [list(x) for x in G] 
    EG = [] 
    for i in xrange(len(G)): 
        for j in range(len(G[i])): 
            if G[i][j] == '0': 
                continue 
            side_list = [] 
            if j+1 <= len(G[i]) - 1: 
                if G[i][j+1] == '1': 
                    index = get_index(i, j+1, G) 
                    side_list.append(index) 
            if j-1 >= 0: 
                if G[i][j-1] == '1': 
                    index = get_index(i, j-1, G) 
                    side_list.append(index) 
            if i+1 <= len(G) - 1: 
                if G[i+1][j] == '1': 
                    index = get_index(i+1, j, G) 
                    side_list.append(index) 
            if i-1 >= 0: 
                if G[i-1][j] == '1': 
                    index = get_index(i-1, j, G) 
                    side_list.append(index) 
            EG.append(side_list) 
    return EG 
def get_matrix(graph): 
    result = [[0]*len(graph) for _ in xrange(len(graph))] 
    for i in xrange(len(graph)): 
        for j in graph[i]: 
            result[i][j] = 1 
    return result 
if __name__ == '__main__': 
    map_list = [ 
        '111111', 
        '101101', 
        '111111', 
        '101101', 
        '111111', 
        '000000' 
    ] 
    G = get_graph(map_list) 
    map_matrix = get_matrix(G) 
    # print map_matrix 
    SP = 14 
    main(map_matrix, SP) 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.