引言：本文將通過Python，用編程解答賽爾號點(diǎn)燃火焰陣一筆畫小游戲，核心算法為深度優(yōu)先搜索（dfs）。

（提示：作為新時(shí)代的好青年，我們要積極傳播積極健康的正能量，所以本文只討論正常游戲方法，不會涉及某個(gè)特殊工具，也請各位小伙伴不要在評論中提及那個(gè)東西，謝謝大家的理解與配合，讓我們一起為促進(jìn)健康良好的游戲氛圍而努力。）

用編程解答賽爾號點(diǎn)燃火焰陣一筆畫小游戲

作者：橙汁

目錄

一. 游戲介紹

二. 概念介紹

三. 解答結(jié)果

四. 程序代碼

游戲介紹

點(diǎn)燃火焰陣是賽爾號2018年7月27日仲夏火焰節(jié)首次登場的小游戲，獲取游戲積分可用于兌換游戲中抗性寶石等道具，于本周五（2019年7月19日）再次重現(xiàn)。

如果通過正常游戲，最多獲得240分。前20關(guān)為普通關(guān)卡，通過后可以獲得當(dāng)前關(guān)卡數(shù)的分?jǐn)?shù)，1+2+3+...+19+20=210；附加關(guān)卡21關(guān)加10分，22關(guān)20分，所以最多是240分。

概念介紹

這個(gè)小游戲的本質(zhì)其實(shí)就是一筆畫問題，這屬于大學(xué)課程離散數(shù)學(xué)/運(yùn)籌學(xué)/拓?fù)鋵W(xué)中圖論章節(jié)的內(nèi)容，也曾經(jīng)在小學(xué)奧數(shù)中涉及過。那么如何求解這類問題呢？

在此先給出兩個(gè)定義：

• 奇頂點(diǎn)，指匯集邊數(shù)為奇數(shù)的頂點(diǎn)；

• 偶頂點(diǎn)，指匯集邊數(shù)為偶數(shù)的頂點(diǎn)。

能夠完成一筆畫的圖形必須具備兩個(gè)條件：

• 圖形是封閉聯(lián)通的；

• 圖形中的奇頂點(diǎn)個(gè)數(shù)為0或2。

一筆畫的方法：

• 如果存在2個(gè)奇頂點(diǎn)，一定是從一個(gè)奇數(shù)點(diǎn)開始畫，到另一個(gè)奇數(shù)點(diǎn)收筆；

• 如果只存在偶頂點(diǎn)，則從任意偶頂點(diǎn)開始，到最后都能完成一筆畫。

以上便是著名數(shù)學(xué)家歐拉提出的“一筆畫定理”，為了紀(jì)念這位偉大的數(shù)學(xué)家，也將能一筆畫出并回到起點(diǎn)的圖稱為歐拉圖。

解答結(jié)果

接下來，就是要展示我們新時(shí)代青年人魅力的時(shí)刻了，使用編程解決這22張圖的一筆畫問題。

之前用C++解題，有小伙伴建議我用Python，所以這次就用Python了。

本次核心算法是dfs，深度優(yōu)先搜索。程序分為函數(shù)與數(shù)據(jù)兩個(gè)部分，編寫成函數(shù)是為了之后遇到其他歐拉圖也可以再接著用。

將小游戲中22張圖的頂點(diǎn)進(jìn)行編號，按照從上到下、從左到右的原則依次編號。

以下展示的就是程序解答的結(jié)果。

【求解第1張圖】

該圖點(diǎn)的個(gè)數(shù)：

4

該圖點(diǎn)的鄰接關(guān)系：

1-2,1-3,2-4,3-4,2-3

該圖的一筆畫的解：

2->1->3->2->4->3

【求解第2張圖】

該圖點(diǎn)的個(gè)數(shù)：

5

該圖點(diǎn)的鄰接關(guān)系：

1-2,1-3,2-3,2-4,3-5,4-5

該圖的一筆畫的解：

2->1->3->2->4->5->3

【求解第3張圖】

該圖點(diǎn)的個(gè)數(shù)：

6

該圖點(diǎn)的鄰接關(guān)系：

1-3,1-4,2-3,3-4,2-5,3-6,5-6

該圖的一筆畫的解：

2->3->1->4->3->6->5->2

【求解第4張圖】

該圖點(diǎn)的個(gè)數(shù)：

5

該圖點(diǎn)的鄰接關(guān)系：

1-3,1-5,2-3,2-5,3-4,4-5

該圖的一筆畫的解：

3->1->5->2->3->4->5

【求解第5張圖】

該圖點(diǎn)的個(gè)數(shù)：

6

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

5

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

8

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

18

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

5

該圖點(diǎn)的鄰接關(guān)系：

1-2,1-3,2-3,2-4,3-4,3-5,4-5

該圖的一筆畫的解：

2->1->3->2->4->3->5->4

【求解第10張圖】

該圖點(diǎn)的個(gè)數(shù)：

12

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

10

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

6

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

12

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

12

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

19

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

8

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

9

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

13

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

13

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

9

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

10

該圖點(diǎn)的鄰接關(guān)系：

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張圖】

該圖點(diǎn)的個(gè)數(shù)：

19

該圖點(diǎn)的鄰接關(guān)系：

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

程序代碼

最后，在這里放上程序的源代碼，希望能夠和大家一起學(xué)習(xí)，進(jìn)步。

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('點(diǎn)的個(gè)數(shù)：\n'))

? ? ? ? else:

? ? ? ? ? ? self.n=eval(myn)

? ? ? ? ? ? print('該圖點(diǎn)的個(gè)數(shù)：\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('點(diǎn)的鄰接關(guān)系：\n')

? ? ? ? else:

? ? ? ? ? ? self.s=mys

? ? ? ? ? ? print('該圖點(diǎn)的鄰接關(guān)系：\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('本程序用于計(jì)算歐拉圖一筆畫最優(yōu)解，輸入點(diǎn)的個(gè)數(shù)與點(diǎn)的鄰接關(guān)系即可。')

? ? print('若點(diǎn)的個(gè)數(shù)輸入0則結(jié)束程序，點(diǎn)的鄰接關(guān)系用“-”連接，用“,”分組。\n')

? ? cmd=input('是否展示調(diào)用示例？(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('示例展示完畢，現(xiàn)在您可以參照示例進(jìn)行操作。\n')

? ? while True:

? ? ? ? try:

? ? ? ? ? ? solveEuler()

? ? ? ? except:

? ? ? ? ? ? print('參數(shù)輸入格式錯誤，請重新輸入。')

if __name__ == "__main__":

? ? main()

附件視頻

課后作業(yè)

@Vesong子韜??既然這位同學(xué)這么喜歡學(xué)習(xí)編程，那么就請他/她自行設(shè)計(jì)一個(gè)歐拉圖，并用程序進(jìn)行解答吧。

? ?