八皇后問(wèn)題描述：在一個(gè)8✖️8的棋盤(pán)上，任意擺放8個(gè)棋子，要求任意兩個(gè)棋子不能在同一行，同一列，同一斜線上，問(wèn)有多少種解法。

規(guī)則分析：

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

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

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

如下圖：

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

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

事實(shí)上，這段代買(mǎi)還可以簡(jiǎn)寫(xiě)，判斷列號(hào)之差也可以寫(xiě)作是列號(hào)之差是否為0，這樣就可以使用一個(gè)in來(lái)完成整個(gè)判斷。修改后如下

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

接下來(lái)寫(xiě)一下擺放棋子的函數(shù)

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

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

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

def arrange_queen(num, queen_tup=list()): ''' :param num:棋盤(pán)的的行數(shù)，當(dāng)然數(shù)值也等于棋盤(pán)的列數(shù) :param queen_tup: 設(shè)置一個(gè)空隊(duì)列，用于保存符合規(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ù)的可以不用看下面的分析了，如果不明白，接下來(lái)我將舉幾個(gè)代碼例子來(lái)說(shuō)明上面的函數(shù)

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

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

但是上述放置棋子的代碼中并沒(méi)用調(diào)用next方法來(lái)執(zhí)行生成器函數(shù)，而是使用了for循環(huán)遍歷，并且在函數(shù)執(zhí)行完畢之后也沒(méi)有拋出StopIteration的錯(cuò)誤。那是因?yàn)閒or循環(huán)在執(zhí)行的時(shí)候，會(huì)不斷的自動(dòng)調(diào)用next方法，并且在遇到StopIteration的時(shí)候會(huì)捕捉異常并終止循環(huán)，以下代碼我將模擬一下for循環(huán)來(lái)執(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 # 實(shí)際的for循環(huán)for i in demo(): ''' for 下的代碼塊 ''' pass

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

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

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ù)嵌套，只能用作計(jì)算3的階乘，我使用它來(lái)理解遞歸函數(shù)

a函數(shù)被調(diào)用執(zhí)行的時(shí)候，傳參3，然后調(diào)用函數(shù)b，同時(shí)傳參3-1=2，函數(shù)b執(zhí)行在調(diào)用函數(shù)c同時(shí)傳參2-1=1，函數(shù)c執(zhí)行，判斷傳參結(jié)果符合，返回?cái)?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ù)的嵌套來(lái)執(zhí)行出3!，那么如果想算10000的函數(shù)呢？難道寫(xiě)10000個(gè)函數(shù)？

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

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

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

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

這就是一個(gè)最簡(jiǎn)單的遞歸函數(shù)

分析函數(shù)的運(yùn)行，函數(shù)第一次被調(diào)用，傳遞參數(shù)3，判斷不滿足終止條件。繼續(xù)執(zhí)行，接下來(lái)再調(diào)用函數(shù)a，傳遞參數(shù)3-1=2，判斷不滿足終止條件。繼續(xù)執(zhí)行，接下來(lái)再調(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é)果返回

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

搞定了含有yield的生成器函數(shù)，for循環(huán)驅(qū)動(dòng)生成器函數(shù)的實(shí)質(zhì)，遞歸函數(shù)的調(diào)用，我們?cè)賮?lái)看八皇后的棋子擺放的函數(shù)，為了方便觀察，將‘八皇后’改為‘四皇后’，就是只算4✖️4棋盤(pán)上放置4個(gè)棋子

def arrange_queen(num, queen_tup=list()): ''' :param num:棋盤(pán)的的行數(shù)，當(dāng)然數(shù)值也等于棋盤(pán)的列數(shù) :param queen_tup: 設(shè)置一個(gè)空隊(duì)列，用于保存符合規(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í)行過(guò)程：

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

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

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

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

.......

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

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

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

整個(gè)代碼為

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:棋盤(pán)的的行數(shù)，當(dāng)然數(shù)值也等于棋盤(pán)的列數(shù) :param queen_tup: 設(shè)置一個(gè)空隊(duì)列，用于保存符合規(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)

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

接下來(lái)我貼出一個(gè)八皇后的的終極版（下面的代碼來(lái)源百度百科），不使用yield關(guān)鍵字的。可以自行理解一下

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]

最后最后，對(duì)比其他語(yǔ)言解決八皇后的代碼量

以上這篇python 使用遞歸回溯完美解決八皇后的問(wèn)題就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持好吧啦網(wǎng)。