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

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

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

規則分析：

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

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

任意兩個棋子不能在同一斜線上，可以把整個棋盤當作是一個XOY平面，原點在棋盤的左上角，斜線的斜率為1或者-1，X為列號，Y為行號，推出斜線的表達式為Y=X+n或者Y=-X+n（n為常數，斜線確定下來之后n就確定了），進而可以推導出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。即判斷兩個棋子是否在同一斜線上，只要判斷出兩個棋子的列號之差是否等于兩個棋子的行號之差的絕對值就行了。

如下圖：

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

def is_rule(queen_tup, new_queen):
 """
 :param queen_tup: 棋子隊列，用于保存已經放置好的棋子，數值代表相應棋子列號
 :param new_queen: 被檢測棋子，數值代表列號
 :return: True表示符合規則，False表示不符合規則
 """
 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):
 """判斷棋子是否符合規則"""
 for index, queen in enumerate(queen_tup):
  if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判斷表達式
   return False
 return True

接下來寫一下擺放棋子的函數

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

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

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

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

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

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

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

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

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

通過這個可以知道，當使用for循環驅動生成器函數的時候，如果函數執行完畢還沒有遇到yield關鍵字，就會直接退出for循環而不會執行for循環下的代碼塊。值得注意的是，上邊兩個循環分別是調用了兩次生成器函數。生成器函數在一次執行完畢之后再繼續調用是不會得到結果的

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

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)

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

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

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

這里發現a函數和b函數除了變量名字不一樣，其余的形式都一摸一樣，那么直接在a里面調用a函數，寫成如下形式

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

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

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

這就是一個最簡單的遞歸函數

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

這就是這個最簡單的遞歸函數的執行過程。總結就是遞歸函數不斷的調用自身，直至滿足函數終止的條件

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

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

執行結果是

[1,3,0,2]

[2,0,3,1]

下面描述一下函數的執行過程：

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

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

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

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

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

6.函數被調用，用于放置第四行，從第一列判斷到最后一列，都不符合規則，函數執行完畢，回到上一級

.......

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

然后第一級函數接著執行，驅動二級函數執行，二級驅動三級執行，三級驅動四級執行....

直到所有結果打印完畢，整個函數執行完畢

整個代碼為

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

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

接下來我貼出一個八皇后的的終極版（下面的代碼來源百度百科），不使用yield關鍵字的。可以自行理解一下

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]

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

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