抖音超火游戏《一笔画完》！到处求教程？我用Python玩通关！

概述 进群：516107834  即可获取数数十套PDF哦！游戏长这样         图形必须是连通的不能有孤立的点。

进群：516107834   即可获取数数十套pdf哦！

游戏长这样

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

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

对游戏进行抽象

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

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

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

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

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

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

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

哈密顿通路

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

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

#! /usr/bin/env python# -*- Coding: utf-8 -*-# Coding with love by Naiquan.import mathimport timestart = time.clock()number = int(740914799/2)marks_List = [True] * (number + 1)marks_List[0] = marks_List[1] = Falsefor i in range(2,int(math.sqrt(number)) + 1): j = i t = j # 去掉倍数 while j * t <= number: marks_List[j * t] = False t += 1elapsed = str(time.clock() - start)print marks_List.count(True)print "Time used:" + elapsed

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

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

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

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

算法设计

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

算法流程：

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

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

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

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

④反复执行 1~3。

算法实现

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

graph = [ [1,19] #25]

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

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

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

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

graph = [ '111111','101101','111111','000000']

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

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 - numdef 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,G) side_list.append(index) if i-1 >= 0: if G[i-1][j] == '1': index = get_index(i-1,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 # 有边则为1 return result

主要的 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,step+1): return True else: used[i] = False # 回溯 返回父节点 path[step] = -1 return Falsedef 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,1)

完整代码如下：

#! /usr/bin/env python# -*- Coding: utf-8 -*-# Coding with love by Naiquan.def dfs(graph,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,step+1): return True else: used[i] = False path[step] = -1 return Falsedef 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,1)def get_index(i,G) sIDe_List.append(index) EG.append(sIDe_List) return EGdef 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 resultif __name__ == '__main__': map_List = [ '111111','000000' ] G = get_graph(map_List) map_matrix = get_matrix(G) # print map_matrix SP = 14 main(map_matrix,SP)

结束

在实现了功能后，我拿着这个程序成功过到了差不多一百关，然后就玩腻了，哈哈哈哈哈哈哈哈哈

总结

以上是内存溢出为你收集整理的抖音超火游戏《一笔画完》！到处求教程？我用Python玩通关！全部内容，希望文章能够帮你解决抖音超火游戏《一笔画完》！到处求教程？我用Python玩通关！所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。