原标题：抖音超火游戏《儿童一筆画画简单的完》！到处求教程我用Python玩通关！

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主要的 DFS 算法如下：

# graph为图的邻接矩阵 used为已访问栈 path为路径栈 step为巳经遍历的顶点的个数

path[0] = v # 表示哈密顿通路的第一个顶点为起点

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