python如何使用遞歸回溯完美解決八皇后的問題

這篇文章主要介紹了python如何使用遞歸回溯完美解決八皇后的問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

八皇后問題描述：在一個8??8的棋盤上，任意擺放8個棋子，要求任意兩個棋子不能在同一行，同一列，同一斜線上，問有多少種解法。

規(guī)則分析：

任意兩個棋子不能在同一行比較好辦，設(shè)置一個隊列，隊列里的每個元素代表一行，就能達(dá)到要求

任意兩個棋子不能在同一列也比較好處理，設(shè)置的隊列里每個元素的數(shù)值代表著每行棋子的列號，比如（0，7，3），表示第一行的棋子放在第一列，第二行的棋子放在第8列，第3行的棋子放在第4列（從0開始計算列號）

任意兩個棋子不能在同一斜線上，可以把整個棋盤當(dāng)作是一個XOY平面，原點在棋盤的左上角，斜線的斜率為1或者-1，X為列號，Y為行號，推出斜線的表達(dá)式為Y=X+n或者Y=-X+n（n為常數(shù)，斜線確定下來之后n就確定了），進而可以推導(dǎo)出Y-X=n或者Y+X=n。也就是說在同一斜線上的兩個棋子行號與列號之和或者之差相等。X1+Y1=X2+Y2或者X1-Y1=X2-Y2。再進行變換能夠得到X1-X2=Y2-Y1或者X1-X2=Y1-Y2，也就是說|X1-Y1|=Y1-Y2。即判斷兩個棋子是否在同一斜線上，只要判斷出兩個棋子的列號之差是否等于兩個棋子的行號之差的絕對值就行了。

如下圖：

將上述文字分析轉(zhuǎn)化為代碼，就可以判斷棋子之間是否符合規(guī)則了（abs(num)表示取num的絕對值）

def is_rule(queen_tup, new_queen):
 """
 :param queen_tup: 棋子隊列，用于保存已經(jīng)放置好的棋子，數(shù)值代表相應(yīng)棋子列號
 :param new_queen: 被檢測棋子，數(shù)值代表列號
 :return: True表示符合規(guī)則，F(xiàn)alse表示不符合規(guī)則
 """
 num = len(queen_tup)
 for index, queen in enumerate(queen_tup):
 
  if new_queen == queen: # 判斷列號是否相等
   return False
  if abs(new_queen-queen) == num-index: # 判斷列號之差絕對值是否與行號之差相等
   return False
 
 return True

事實上，這段代買還可以簡寫，判斷列號之差也可以寫作是列號之差是否為0，這樣就可以使用一個in來完成整個判斷。修改后如下

def is_rule(queen_tup, new_queen):
 """判斷棋子是否符合規(guī)則"""
 for index, queen in enumerate(queen_tup):
  if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判斷表達(dá)式
   return False
 return True

接下來寫一下擺放棋子的函數(shù)

擺放棋子其實有兩種方法，第一種，求出8??8棋盤上每行放置一個棋子的所有方法，也就相當(dāng)于全排列。然后再用沖突函數(shù)逐個判斷是否符合規(guī)則，如符合就放入隊列

第二種，在一行放入棋子，然后判斷是否符合規(guī)則，符合的情況下再去放下一行，下一行如果所有位置都不符合，退回到上一行，上一行的棋子再放置一個新的位置，然后再進去下一行判斷有沒有符合規(guī)則的棋子的位置。這種方法叫做遞歸回溯，每一行就相當(dāng)于是一個回溯點

這里我使用第二種方法寫個函數(shù)，先上代碼，然后再解釋

def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盤的的行數(shù)，當(dāng)然數(shù)值也等于棋盤的列數(shù)
 :param queen_tup: 設(shè)置一個空隊列，用于保存符合規(guī)則的棋子的信息
 """
 
 for new_queen in range(num): # 遍歷一行棋子的每一列
 
  if is_rule(queen_tup, new_queen): # 判斷是否沖突
 
   if len(queen_tup) == num-1:  # 判斷是否是最后一行
    yield [new_queen] # yield關(guān)鍵字
 
   else:
    # 若果不是最后一行，遞歸函數(shù)接著放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result

如果能夠理解上邊函數(shù)的可以不用看下面的分析了，如果不明白，接下來我將舉幾個代碼例子來說明上面的函數(shù)

首先是yield，這個是python里的關(guān)鍵字，帶有yield的函數(shù)被稱作為生成器函數(shù)。函數(shù)在執(zhí)行的時候，遇到y(tǒng)ield關(guān)鍵字會暫停函數(shù)的執(zhí)行，同時返回yield右邊的對象到函數(shù)被調(diào)用的地方，直到函數(shù)下次被執(zhí)行，將回到y(tǒng)ield所在的地方繼續(xù)執(zhí)行，如果函數(shù)執(zhí)行完畢還沒有遇到y(tǒng)ield，就會拋出一個異常StopIteration。而生成器函數(shù)需要使用next方法來執(zhí)行。下面的代碼將解釋生成器函數(shù)的執(zhí)行：

def demo():
 
 yield 1
 yield 2
 print('end')
 
b = demo()  # 將生成器函數(shù)的引用傳遞給變量b
print(next(b)) # 第一次執(zhí)行生成器函數(shù)，返回 1 同時函數(shù)暫停，打印結(jié)果
print(next(b)) # 第二次執(zhí)行生成器函數(shù)，返回 2 同時函數(shù)暫停，打印結(jié)果
print(next(b)) # 第三次執(zhí)行生成器函數(shù)，因為沒有再遇到y(tǒng)ield，函數(shù)執(zhí)行完畢，拋出異常StopIteration

但是上述放置棋子的代碼中并沒用調(diào)用next方法來執(zhí)行生成器函數(shù)，而是使用了for循環(huán)遍歷，并且在函數(shù)執(zhí)行完畢之后也沒有拋出StopIteration的錯誤。那是因為for循環(huán)在執(zhí)行的時候，會不斷的自動調(diào)用next方法，并且在遇到StopIteration的時候會捕捉異常并終止循環(huán)，以下代碼我將模擬一下for循環(huán)來執(zhí)行生成器函數(shù)

def demo():
 
 yield 1
 yield 2
 print('end')
 
 
# 模擬的for循環(huán)
b = demo()
while True:
 try:
  next(b)
  """
  此段區(qū)域?qū)慺or下的代碼塊
  """
 except StopIteration:
  break
 
# 實際的for循環(huán)
for i in demo():
 """
 for 下的代碼塊
 """
 pass

通過這個可以知道，當(dāng)使用for循環(huán)驅(qū)動生成器函數(shù)的時候，如果函數(shù)執(zhí)行完畢還沒有遇到y(tǒng)ield關(guān)鍵字，就會直接退出for循環(huán)而不會執(zhí)行for循環(huán)下的代碼塊。值得注意的是，上邊兩個循環(huán)分別是調(diào)用了兩次生成器函數(shù)。生成器函數(shù)在一次執(zhí)行完畢之后再繼續(xù)調(diào)用是不會得到結(jié)果的

了解了生成器函數(shù)與for循環(huán)是怎么驅(qū)動生成器函數(shù)之后，關(guān)于棋子的遞歸函數(shù)里面還有一個就是遞歸函數(shù)了。以前上課的時候老師將遞歸函數(shù)使用的例子是數(shù)值的階乘，這里我也使用階乘來解釋一下遞歸函數(shù)的執(zhí)行。先介紹一下階乘：給定一個正整數(shù)n，規(guī)定n的階乘n!=n(n-1)(n-2).....1。也就是從1到n的累乘。（0!=1，這是規(guī)定，別問我為什么......）

def a(num):
 result = num*b(num-1)
 return result
 
 
def b(num):
 
 result = num*c(num-1)
 return result
 
 
def c(num):
 if num == 1:
  result = 1
 return result
 
 
result = a(3)
print(result)

上述代碼是函數(shù)嵌套，只能用作計算3的階乘，我使用它來理解遞歸函數(shù)

a函數(shù)被調(diào)用執(zhí)行的時候，傳參3，然后調(diào)用函數(shù)b，同時傳參3-1=2，函數(shù)b執(zhí)行在調(diào)用函數(shù)c同時傳參2-1=1，函數(shù)c執(zhí)行，判斷傳參結(jié)果符合，返回數(shù)值result到函數(shù)c被調(diào)用的地方,然后與b的參數(shù)2相乘，得到新的結(jié)果賦值給b里面的result，然后再將result返回到b被調(diào)用的地方，再乘a的參數(shù)3賦值給a里面的result，再將a里的result返回到函數(shù)a被調(diào)用的地方，然后打印結(jié)果。

這就是利用函數(shù)的嵌套來執(zhí)行出3!，那么如果想算10000的函數(shù)呢？難道寫10000個函數(shù)？

這里發(fā)現(xiàn)a函數(shù)和b函數(shù)除了變量名字不一樣，其余的形式都一摸一樣，那么直接在a里面調(diào)用a函數(shù)，寫成如下形式

def a(num):
 result = num*a(num-1)
 return result

但是這樣的話，函數(shù)將不斷的被調(diào)用。所以加一個函數(shù)終止的條件，變成了

def a(num):
 if num == 1:
  return 1
 else:
  return num*a(num-1)
 
 
result = a(3)
print(result)

這就是一個最簡單的遞歸函數(shù)

分析函數(shù)的運行，函數(shù)第一次被調(diào)用，傳遞參數(shù)3，判斷不滿足終止條件。繼續(xù)執(zhí)行，接下來再調(diào)用函數(shù)a，傳遞參數(shù)3-1=2，判斷不滿足終止條件。繼續(xù)執(zhí)行，接下來再調(diào)用函數(shù)a，傳遞參數(shù)2-1=1，判斷滿足終止條件，第三次被調(diào)用的函數(shù)結(jié)束，返回1到被調(diào)用的地方，與2相乘，第二次被調(diào)用的函數(shù)結(jié)束，結(jié)果再返回到第二次函數(shù)被調(diào)用的地方，與3相乘，第一次被調(diào)用的函數(shù)結(jié)束，結(jié)果返回

這就是這個最簡單的遞歸函數(shù)的執(zhí)行過程。總結(jié)就是遞歸函數(shù)不斷的調(diào)用自身，直至滿足函數(shù)終止的條件

搞定了含有yield的生成器函數(shù)，for循環(huán)驅(qū)動生成器函數(shù)的實質(zhì)，遞歸函數(shù)的調(diào)用，我們再來看八皇后的棋子擺放的函數(shù)，為了方便觀察，將‘八皇后'改為‘四皇后'，就是只算4??4棋盤上放置4個棋子

def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盤的的行數(shù)，當(dāng)然數(shù)值也等于棋盤的列數(shù)
 :param queen_tup: 設(shè)置一個空隊列，用于保存符合規(guī)則的棋子的信息
 """
 
 for new_queen in range(num): # 遍歷一行棋子的每一列
 
  if is_rule(queen_tup, new_queen): # 判斷是否沖突
 
   if len(queen_tup) == num-1:  # 判斷是否是最后一行
    yield [new_queen] # yield關(guān)鍵字
 
   else:
    # 若果不是最后一行，遞歸函數(shù)接著放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result
 
 
for i in arrange_queen(4):
 print(i)

執(zhí)行結(jié)果是

[1,3,0,2]

[2,0,3,1]

下面描述一下函數(shù)的執(zhí)行過程：

1.放置第一行棋子。函數(shù)第一次被調(diào)用，傳遞參數(shù)4，空列表。放置棋子在第一行第一列，判斷棋子放置符合規(guī)則，判斷不是最后一行，將棋子位置信息放入列表，同時生成新的列表[0]

2.放置第二行棋子。函數(shù)第二次被調(diào)用，傳遞參數(shù)4，列表[0]。放置棋子在第二行第一列，判斷棋子不符合規(guī)則，接著放置棋子在第二行第二列，判斷棋子不符合規(guī)則，再放置棋子在第二行第三列，判斷符合規(guī)則，將棋子位置信息放入列表，同時生成新的列表[0，2]

3.放置第三行棋子。函數(shù)第三次被調(diào)用，傳遞參數(shù)4，列表[0,2]。放置棋子在第三行第一列，判斷棋子不符合規(guī)則，接著放置棋子在第三行第二列，判斷不符合規(guī)則，再放置棋子到第三行第三列，判斷不符合規(guī)則，再放置棋子到第三行第四列，判斷還是不符合規(guī)則。第三次函數(shù)調(diào)用結(jié)束

4.回到函數(shù)第二次被調(diào)用的地方，第二次被調(diào)用的函數(shù)接著放置棋子，上一次放置到了第三列，這次放到第四列，判斷符合規(guī)則，將棋子位置信息放入列表，同時生成新的列表[0,3]

5.函數(shù)被調(diào)用，用于放置第三行，從第一列再依次判斷到最后一列，如果符合規(guī)則，放入棋子信息，同時生成新的列表[0,3,1]

6.函數(shù)被調(diào)用，用于放置第四行，從第一列判斷到最后一列，都不符合規(guī)則，函數(shù)執(zhí)行完畢，回到上一級

.......

N.當(dāng)前三行的棋子放入都符合規(guī)則，而且第四行也符合規(guī)則了，此時第一次遇到y(tǒng)ield關(guān)鍵字，第四級函數(shù)暫停，將棋子信息放入列表[2]，返回到第三級，第三級函數(shù)也將第三級符合規(guī)則的棋子信息放入列表，同時與第四級返回的列表相加，得到一個新的列表，然后遇到第三級函數(shù)的關(guān)鍵字函數(shù)yield，第三級函數(shù)暫停，返回了[0,2]到第二級函數(shù).......直到第一級函數(shù)暫停，返回結(jié)果[1,3,0,2]，打印結(jié)果

然后第一級函數(shù)接著執(zhí)行，驅(qū)動二級函數(shù)執(zhí)行，二級驅(qū)動三級執(zhí)行，三級驅(qū)動四級執(zhí)行....

直到所有結(jié)果打印完畢，整個函數(shù)執(zhí)行完畢

整個代碼為

def is_rule(queen_tup, new_queen):
 """判斷棋子是否符合規(guī)則"""
 for index, queen in enumerate(queen_tup):
  if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判斷表達(dá)式
   return False
 return True
 
 
def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盤的的行數(shù)，當(dāng)然數(shù)值也等于棋盤的列數(shù)
 :param queen_tup: 設(shè)置一個空隊列，用于保存符合規(guī)則的棋子的信息
 """
 
 for new_queen in range(num): # 遍歷一行棋子的每一列
 
  if is_rule(queen_tup, new_queen): # 判斷是否沖突
 
   if len(queen_tup) == num-1:  # 判斷是否是最后一行
    yield [new_queen] # yield關(guān)鍵字
 
   else:
    # 若果不是最后一行，遞歸函數(shù)接著放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result
 
 
for i in arrange_queen(8):
 print(i)

整個代碼最終要的就是遞歸回溯的思想，如果能真正的明白，不用用什么語法或者寫什么樣的函數(shù)，都能輕松解決這個八皇后的問題

接下來我貼出一個八皇后的的終極版（下面的代碼來源百度百科），不使用yield關(guān)鍵字的?？梢宰孕欣斫庖幌?/p>

def queen(A, cur=0):
 if cur == len(A):
  print(A)
  return 0
 for col in range(len(A)):
  A[cur], flag = col, True
  for row in range(cur):
   if A[row] == col or abs(col - A[row]) == cur - row:
    flag = False
    break
  if flag:
   queen(A, cur+1)
queen([None]*8)

八皇后的所有解

[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
[0, 6, 4, 7, 1, 3, 5, 2]
[1, 3, 5, 7, 2, 0, 6, 4]
[1, 4, 6, 0, 2, 7, 5, 3]
[1, 4, 6, 3, 0, 7, 5, 2]
[1, 5, 0, 6, 3, 7, 2, 4]
[1, 5, 7, 2, 0, 3, 6, 4]
[1, 6, 2, 5, 7, 4, 0, 3]
[1, 6, 4, 7, 0, 3, 5, 2]
[1, 7, 5, 0, 2, 4, 6, 3]
[2, 0, 6, 4, 7, 1, 3, 5]
[2, 4, 1, 7, 0, 6, 3, 5]
[2, 4, 1, 7, 5, 3, 6, 0]
[2, 4, 6, 0, 3, 1, 7, 5]
[2, 4, 7, 3, 0, 6, 1, 5]
[2, 5, 1, 4, 7, 0, 6, 3]
[2, 5, 1, 6, 0, 3, 7, 4]
[2, 5, 1, 6, 4, 0, 7, 3]
[2, 5, 3, 0, 7, 4, 6, 1]
[2, 5, 3, 1, 7, 4, 6, 0]
[2, 5, 7, 0, 3, 6, 4, 1]
[2, 5, 7, 0, 4, 6, 1, 3]
[2, 5, 7, 1, 3, 0, 6, 4]
[2, 6, 1, 7, 4, 0, 3, 5]
[2, 6, 1, 7, 5, 3, 0, 4]
[2, 7, 3, 6, 0, 5, 1, 4]
[3, 0, 4, 7, 1, 6, 2, 5]
[3, 0, 4, 7, 5, 2, 6, 1]
[3, 1, 4, 7, 5, 0, 2, 6]
[3, 1, 6, 2, 5, 7, 0, 4]
[3, 1, 6, 2, 5, 7, 4, 0]
[3, 1, 6, 4, 0, 7, 5, 2]
[3, 1, 7, 4, 6, 0, 2, 5]
[3, 1, 7, 5, 0, 2, 4, 6]
[3, 5, 0, 4, 1, 7, 2, 6]
[3, 5, 7, 1, 6, 0, 2, 4]
[3, 5, 7, 2, 0, 6, 4, 1]
[3, 6, 0, 7, 4, 1, 5, 2]
[3, 6, 2, 7, 1, 4, 0, 5]
[3, 6, 4, 1, 5, 0, 2, 7]
[3, 6, 4, 2, 0, 5, 7, 1]
[3, 7, 0, 2, 5, 1, 6, 4]
[3, 7, 0, 4, 6, 1, 5, 2]
[3, 7, 4, 2, 0, 6, 1, 5]
[4, 0, 3, 5, 7, 1, 6, 2]
[4, 0, 7, 3, 1, 6, 2, 5]
[4, 0, 7, 5, 2, 6, 1, 3]
[4, 1, 3, 5, 7, 2, 0, 6]
[4, 1, 3, 6, 2, 7, 5, 0]
[4, 1, 5, 0, 6, 3, 7, 2]
[4, 1, 7, 0, 3, 6, 2, 5]
[4, 2, 0, 5, 7, 1, 3, 6]
[4, 2, 0, 6, 1, 7, 5, 3]
[4, 2, 7, 3, 6, 0, 5, 1]
[4, 6, 0, 2, 7, 5, 3, 1]
[4, 6, 0, 3, 1, 7, 5, 2]
[4, 6, 1, 3, 7, 0, 2, 5]
[4, 6, 1, 5, 2, 0, 3, 7]
[4, 6, 1, 5, 2, 0, 7, 3]
[4, 6, 3, 0, 2, 7, 5, 1]
[4, 7, 3, 0, 2, 5, 1, 6]
[4, 7, 3, 0, 6, 1, 5, 2]
[5, 0, 4, 1, 7, 2, 6, 3]
[5, 1, 6, 0, 2, 4, 7, 3]
[5, 1, 6, 0, 3, 7, 4, 2]
[5, 2, 0, 6, 4, 7, 1, 3]
[5, 2, 0, 7, 3, 1, 6, 4]
[5, 2, 0, 7, 4, 1, 3, 6]
[5, 2, 4, 6, 0, 3, 1, 7]
[5, 2, 4, 7, 0, 3, 1, 6]
[5, 2, 6, 1, 3, 7, 0, 4]
[5, 2, 6, 1, 7, 4, 0, 3]
[5, 2, 6, 3, 0, 7, 1, 4]
[5, 3, 0, 4, 7, 1, 6, 2]
[5, 3, 1, 7, 4, 6, 0, 2]
[5, 3, 6, 0, 2, 4, 1, 7]
[5, 3, 6, 0, 7, 1, 4, 2]
[5, 7, 1, 3, 0, 6, 4, 2]
[6, 0, 2, 7, 5, 3, 1, 4]
[6, 1, 3, 0, 7, 4, 2, 5]
[6, 1, 5, 2, 0, 3, 7, 4]
[6, 2, 0, 5, 7, 4, 1, 3]
[6, 2, 7, 1, 4, 0, 5, 3]
[6, 3, 1, 4, 7, 0, 2, 5]
[6, 3, 1, 7, 5, 0, 2, 4]
[6, 4, 2, 0, 5, 7, 1, 3]
[7, 1, 3, 0, 6, 4, 2, 5]
[7, 1, 4, 2, 0, 6, 3, 5]
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]

最后最后，對比其他語言解決八皇后的代碼量

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“python如何使用遞歸回溯完美解決八皇后的問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!