赛尔号点燃火焰阵小游戏编程解答
引言：本文将通过Python，用编程解答赛尔号点燃火焰阵一笔画小游戏，核心算法为深度优先搜索（dfs）。
（提示：作为新时代的好青年，我们要积极传播积极健康的正能量，所以本文只讨论正常游戏方法，不会涉及某个特殊工具，也请各位小伙伴不要在评论中提及那个东西，谢谢大家的理解与配合，让我们一起为促进健康良好的游戏氛围而努力。）
用编程解答赛尔号点燃火焰阵一笔画小游戏
作者：橙汁
目录
一. 游戏介绍
二. 概念介绍
三. 解答结果
四. 程序代码
游戏介绍
点燃火焰阵是赛尔号2018年7月27日仲夏火焰节首次登场的小游戏，获取游戏积分可用于兑换游戏中抗性宝石等道具，于本周五（2019年7月19日）再次重现。
如果通过正常游戏，最多获得240分。前20关为普通关卡，通过后可以获得当前关卡数的分数，1+2+3+...+19+20=210；附加关卡21关加10分，22关20分，所以最多是240分。
概念介绍
这个小游戏的本质其实就是一笔画问题，这属于大学课程离散数学/运筹学/拓扑学中图论章节的内容，也曾经在小学奥数中涉及过。那么如何求解这类问题呢？
在此先给出两个定义：
奇顶点，指汇集边数为奇数的顶点；
偶顶点，指汇集边数为偶数的顶点。
能够完成一笔画的图形必须具备两个条件：
图形是封闭联通的；
图形中的奇顶点个数为0或2。
一笔画的方法：
如果存在2个奇顶点，一定是从一个奇数点开始画，到另一个奇数点收笔；
如果只存在偶顶点，则从任意偶顶点开始，到最后都能完成一笔画。
以上便是著名数学家欧拉提出的“一笔画定理”，为了纪念这位伟大的数学家，也将能一笔画出并回到起点的图称为欧拉图。
解答结果
接下来，就是要展示我们新时代青年人魅力的时刻了，使用编程解决这22张图的一笔画问题。
之前用C++解题，有小伙伴建议我用Python，所以这次就用Python了。
本次核心算法是dfs，深度优先搜索。程序分为函数与数据两个部分，编写成函数是为了之后遇到其他欧拉图也可以再接着用。
将小游戏中22张图的顶点进行编号，按照从上到下、从左到右的原则依次编号。
以下展示的就是程序解答的结果。
【求解第1张图】
该图点的个数：
4
该图点的邻接关系：
1-2,1-3,2-4,3-4,2-3
该图的一笔画的解：
2->1->3->2->4->3
【求解第2张图】
该图点的个数：
5
该图点的邻接关系：
1-2,1-3,2-3,2-4,3-5,4-5
该图的一笔画的解：
2->1->3->2->4->5->3
【求解第3张图】
该图点的个数：
6
该图点的邻接关系：
1-3,1-4,2-3,3-4,2-5,3-6,5-6
该图的一笔画的解：
2->3->1->4->3->6->5->2
【求解第4张图】
该图点的个数：
5
该图点的邻接关系：
1-3,1-5,2-3,2-5,3-4,4-5
该图的一笔画的解：
3->1->5->2->3->4->5
【求解第5张图】
该图点的个数：
6
该图点的邻接关系：
1-2,1-4,2-5,3-4,3-5,4-5,4-6,5-6
该图的一笔画的解：
2->1->4->3->5->4->6->5->2
【求解第6张图】
该图点的个数：
5
该图点的邻接关系：
1-2,1-3,2-3,2-4,2-5,3-4,3-5,4-5
该图的一笔画的解：
4->2->1->3->2->5->3->4->5
【求解第7张图】
该图点的个数：
8
该图点的邻接关系：
1-2,1-4,2-3,2-4,2-5,2-7,3-5,4-6,4-7,5-7,5-8,6-7,7-8
该图的一笔画的解：
2->1->4->2->3->5->2->7->4->6->7->5->8->7
【求解第8张图】
该图点的个数：
18
该图点的邻接关系：
1-2,1-10,2-4,3-4,3-11,4-5,4-7,5-8,6-7,6-12,7-8,7-13,8-9,8-16,9-18,10-11,11-12,11-14,12-13,12-15,14-15,15-16,15-17,17-18
该图的一笔画的解：
2->1->10->11->3->4->5->8->7->6->12->11->14->15->16->8->9->18->17->15->12->13->7->4->2
【求解第9张图】
该图点的个数：
5
该图点的邻接关系：
1-2,1-3,2-3,2-4,3-4,3-5,4-5
该图的一笔画的解：
2->1->3->2->4->3->5->4
【求解第10张图】
该图点的个数：
12
该图点的邻接关系：
1-2,1-4,2-5,3-4,3-7,4-5,4-8,4-9,5-6,5-8,5-9,6-10,7-8,8-11,9-10,9-12,11-12
该图的一笔画的解：
4->1->2->5->4->3->7->8->4->9->5->6->10->9->12->11->8->5
【求解第11张图】
该图点的个数：
10
该图点的邻接关系：
1-3,1-4,2-3,2-5,3-4,3-5,3-8,3-9,4-5,4-6,4-8,4-9,5-7,5-8,5-9,6-8,7-9,8-9,8-10,9-10
该图的一笔画的解：
2->3->1->4->3->5->4->6->8->3->9->4->8->5->7->9->8->10->9->5->2
【求解第12张图】
该图点的个数：
6
该图点的邻接关系：
1-2,1-3,1-5,2-3,2-4,2-5,3-5,3-6,4-5,5-6
该图的一笔画的解：
1->2->3->1->5->2->4->5->3->6->5
【求解第13张图】
该图点的个数：
12
该图点的邻接关系：
1-3,1-4,2-3,3-4,4-5,2-6,3-6,4-7,5-7,6-8,6-9,8-9,7-10,7-11,9-10,10-11,9-12,10-12
该图的一笔画的解：
2->3->1->4->3->6->8->9->10->7->4->5->7->11->10->12->9->6->2
【求解第14张图】
该图点的个数：
12
该图点的邻接关系：
1-2,1-4,2-3,2-4,2-5,3-5,3-6,4-5,4-7,5-6,5-7,5-8,6-8,6-9,7-8,7-10,8-9,8-10,8-11,9-11,9-12,10-11,11-12
该图的一笔画的解：
3->2->1->4->2->5->3->6->5->4->7->5->8->6->9->8->7->10->8->11->9->12->11->10
【求解第15张图】
该图点的个数：
19
该图点的邻接关系：
1-4,1-9,2-4,2-5,3-5,3-11,4-6,4-7,5-6,5-8,6-7,6-8,7-9,7-10,8-10,8-11,9-12,9-17,10-12,10-13,11-13,11-19,12-14,12-15,13-14,13-16,14-15,14-16,15-17,15-18,16-18,16-19
该图的一笔画的解：
2->4->1->9->7->4->6->5->3->11->8->6->7->10->12->9->17->15->12->14->13->11->19->16->14->15->18->16->13->10->8->5->2
【求解第16张图】
该图点的个数：
8
该图点的邻接关系：
1-6,1-7,2-3,2-5,2-6,2-8,3-4,3-7,3-8,4-7,5-6,6-7
该图的一笔画的解：
2->3->4->7->1->6->2->5->6->7->3->8->2
【求解第17张图】
该图点的个数：
9
该图点的邻接关系：
1-2,1-4,2-3,2-5,2-6,3-4,3-5,3-7,4-6,4-7,5-6,5-8,6-7,6-8,6-9,7-9
该图的一笔画的解：
2->1->4->3->2->5->3->7->4->6->5->8->6->7->9->6->2
【求解第18张图】
该图点的个数：
13
该图点的邻接关系：
1-2,1-4,2-3,2-5,2-6,3-4,3-5,3-6,3-7,4-6,4-7,5-6,5-9,6-7,6-8,6-9,6-10,7-9,8-9,8-11,9-10,9-11,9-13,10-12,10-13,8-12
该图的一笔画的解：
3->2->1->4->3->5->2->6->3->7->4->6->5->9->6->7->9->8->6->10->9->11->8->12->10->13->9
【求解第19张图】
该图点的个数：
13
该图点的邻接关系：
1-2,1-3,2-3,2-4,2-5,2-6,3-5,3-6,3-7,4-5,5-6,5-9,5-10,6-7,6-9,6-10,8-9,8-12,9-10,9-12,9-13,10-11,10-12,10-13,11-13,12-13
该图的一笔画的解：
2->1->3->2->4->5->2->6->3->5->6->9->5->10->9->8->12->9->13->10->11->13->12->10->6->7->3
【求解第20张图】
该图点的个数：
9
该图点的邻接关系：
1-2,1-3,1-7,2-4,2-5,2-6,3-4,4-5,4-8,5-6,5-8,6-7,6-8,7-9,8-9
该图的一笔画的解：
1->2->4->3->1->7->6->2->5->4->8->5->6->8->9->7
【求解第21张图】
该图点的个数：
10
该图点的邻接关系：
1-2,1-3,2-3,3-6,3-7,3-10,4-6,4-8,5-7,5-9,6-10,7-9,7-10,8-6
该图的一笔画的解：
3->1->2->3->6->4->8->6->10->3->7->5->9->7->10
【求解第22张图】
该图点的个数：
19
该图点的邻接关系：
1-4,1-6,2-4,2-5,3-5,4-8,3-7,4-6,5-7,5-8,8-10,8-11,10-14,9-10,9-13,10-13,11-12,11-14,11-15,12-15,14-16,14-17,14-18,14-19,16-17,18-19
该图的一笔画的解：
2->4->1->6->4->8->10->9->13->10->14->16->17->14->18->19->14->11->12->15->11->8->5->3->7->5->2
程序代码
最后，在这里放上程序的源代码，希望能够和大家一起学习，进步。
class solveEuler:
a=[[]]
b=[]
k=0
n=100
s=''
def __init__(self,myn='',mys='',myi=''):
myn=str(myn)
myi=str(myi)
if myi=='':
print('【求解一张图】')
else:
print('【求解第'+str(myi)+'张图】')
if myn=='':
self.n=eval(input('点的个数：\n'))
else:
self.n=eval(myn)
print('该图点的个数：\n'+str(self.n))
if self.n==0:
exit()
self.a=[[0 for j in range(self.n+1)] for i in range(self.n+1)]
self.b=[0 for i in range(self.n**2+1)]
if mys=='':
self.s=input('点的邻接关系：\n')
else:
self.s=mys
print('该图点的邻接关系：\n'+self.s)
print(self.solveMe())
def dfs(self,m):
for i in range(self.n):
if self.a[m][i]==1:
self.a[m][i]=0
self.a[i][m]=0
self.dfs(i)
self.k+=1
self.b[self.k]=m+1;
def solveMe(self):
i=0
j=0
sum1=0
sum2=0
f=1
ss=self.s.split(',')
for i in range(len(ss)):
sss=ss[i].split('-')
self.a[int(sss[0])-1][int(sss[1])-1]=1
self.a[int(sss[1])-1][int(sss[0])-1]=1
for i in range(self.n):
sum1=0
for j in range(self.n):
if self.a[i][j] == 1:
sum1+=1
if sum1%2==1:
if sum2==0:
f=i
sum2+=1
if (sum2>2 or sum2==1):
return '该图的一笔画无解！'
else:
self.dfs(f)
result='该图的一笔画的解：\n'
for i in range(self.k):
if i<self.k-1:
result+=(str(self.b[self.k-i])+'->')
else:
result+=(str(self.b[self.k-i])+'\n')
return result
def main():
print('本程序用于计算欧拉图一笔画最优解，输入点的个数与点的邻接关系即可。')
print('若点的个数输入0则结束程序，点的邻接关系用“-”连接，用“,”分组。\n')
cmd=input('是否展示调用示例？(y/n)：').upper()
if (cmd=='Y' or cmd=='YES'):
Euler=[
[4,'1-2,1-3,2-4,3-4,2-3',1],
[5,'1-2,1-3,2-3,2-4,3-5,4-5',2],
[6,'1-3,1-4,2-3,3-4,2-5,3-6,5-6',3],
[5,'1-3,1-5,2-3,2-5,3-4,4-5',4],
[6,'1-2,1-4,2-5,3-4,3-5,4-5,4-6,5-6',5],
[5,'1-2,1-3,2-3,2-4,2-5,3-4,3-5,4-5',6],
[8,'1-2,1-4,2-3,2-4,2-5,2-7,3-5,4-6,4-7,5-7,5-8,6-7,7-8',7],
[18,'1-2,1-10,2-4,3-4,3-11,4-5,4-7,5-8,6-7,6-12,7-8,7-13,8-9,8-16,9-18,10-11,11-12,11-14,12-13,12-15,14-15,15-16,15-17,17-18',8],
[5,'1-2,1-3,2-3,2-4,3-4,3-5,4-5',9],
[12,'1-2,1-4,2-5,3-4,3-7,4-5,4-8,4-9,5-6,5-8,5-9,6-10,7-8,8-11,9-10,9-12,11-12',10],
[10,'1-3,1-4,2-3,2-5,3-4,3-5,3-8,3-9,4-5,4-6,4-8,4-9,5-7,5-8,5-9,6-8,7-9,8-9,8-10,9-10',11],
[6,'1-2,1-3,1-5,2-3,2-4,2-5,3-5,3-6,4-5,5-6',12],
[12,'1-3,1-4,2-3,3-4,4-5,2-6,3-6,4-7,5-7,6-8,6-9,8-9,7-10,7-11,9-10,10-11,9-12,10-12',13],
[12,'1-2,1-4,2-3,2-4,2-5,3-5,3-6,4-5,4-7,5-6,5-7,5-8,6-8,6-9,7-8,7-10,8-9,8-10,8-11,9-11,9-12,10-11,11-12',14],
[19,'1-4,1-9,2-4,2-5,3-5,3-11,4-6,4-7,5-6,5-8,6-7,6-8,7-9,7-10,8-10,8-11,9-12,9-17,10-12,10-13,11-13,11-19,12-14,12-15,13-14,13-16,14-15,14-16,15-17,15-18,16-18,16-19',15],
[8,'1-6,1-7,2-3,2-5,2-6,2-8,3-4,3-7,3-8,4-7,5-6,6-7',16],
[9,'1-2,1-4,2-3,2-5,2-6,3-4,3-5,3-7,4-6,4-7,5-6,5-8,6-7,6-8,6-9,7-9',17],
[13,'1-2,1-4,2-3,2-5,2-6,3-4,3-5,3-6,3-7,4-6,4-7,5-6,5-9,6-7,6-8,6-9,6-10,7-9,8-9,8-11,9-10,9-11,9-13,10-12,10-13,8-12',18],
[13,'1-2,1-3,2-3,2-4,2-5,2-6,3-5,3-6,3-7,4-5,5-6,5-9,5-10,6-7,6-9,6-10,8-9,8-12,9-10,9-12,9-13,10-11,10-12,10-13,11-13,12-13',19],
[9,'1-2,1-3,1-7,2-4,2-5,2-6,3-4,4-5,4-8,5-6,5-8,6-7,6-8,7-9,8-9',20],
[10,'1-2,1-3,2-3,3-6,3-7,3-10,4-6,4-8,5-7,5-9,6-10,7-9,7-10,8-6',21],
[19,'1-4,1-6,2-4,2-5,3-5,4-8,3-7,4-6,5-7,5-8,8-10,8-11,10-14,9-10,9-13,10-13,11-12,11-14,11-15,12-15,14-16,14-17,14-18,14-19,16-17,18-19',22]
]
for item in Euler:
solveEuler(item[0],item[1],item[2])
print('示例展示完毕，现在您可以参照示例进行操作。\n')
while True:
try:
solveEuler()
except:
print('参数输入格式错误，请重新输入。')
if __name__ == "__main__":
main()
附件视频
课后作业
@Vesong子韬 既然这位同学这么喜欢学习编程，那么就请他/她自行设计一个欧拉图，并用程序进行解答吧。
