您好,登錄后才能下訂單哦!
小編給大家分享一下Python如何解決八皇后問題,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
具體如下:
八皇后問題是一個以國際象棋為背景的問題:如何能夠在 8×8 的國際象棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達(dá)到此目的,任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題:這時棋盤的大小變?yōu)閚1×n1,而皇后個數(shù)也變成n2。而且僅當(dāng) n2 = 1 或 n1 ≥ 3 時問題有解。
這是一個典型的回溯算法,我們可以將問題進(jìn)行分解:
首先,我們要想到某種方法來解決沖突檢測問題,即不能令棋子處于能相互吃掉的位置——相鄰、左右對角線。
其次,運用回溯的方法,求得問題的解。此處具體為函數(shù)的遞歸調(diào)用,當(dāng)調(diào)用到棋盤的最后一行,便跳出,求得解。
最后,將我們的解打印出來。難點在于對遞歸調(diào)用函數(shù)的理解。
這僅僅是思路,是我們必須要解決的問題,但并不代表程序的運行流程。
具體代碼如下:
#-*- coding:utf-8 -*- import random #沖突檢查,在定義state時,采用state來標(biāo)志每個皇后的位置,其中索引用來表示橫坐標(biāo),基對應(yīng)的值表示縱坐標(biāo),例如: state[0]=3,表示該皇后位于第1行的第4列上 def conflict(state, nextX): nextY = len(state) # print(nextY), for i in range(nextY): #如果下一個皇后的位置與當(dāng)前的皇后位置相鄰(包括上下,左右)或在同一對角線上,則說明有沖突,需要重新擺放 if abs(state[i]-nextX) in (0, nextY-i): #縱坐標(biāo)減去下一個皇后的橫坐標(biāo)的絕對值 處于 0到下一皇后縱坐標(biāo)減i則沖突 return True return False #采用生成器的方式來產(chǎn)生每一個皇后的位置,并用遞歸來實現(xiàn)下一個皇后的位置。 def queens(num, state=()): #num = 8 # print("%d "%len(state)), for pos in range(num): if not conflict(state, pos): #如果沒有沖突 #產(chǎn)生當(dāng)前皇后的位置信息 if len(state) == num-1: yield (pos, ) #生成元組 #否則,把當(dāng)前皇后的位置信息,添加到狀態(tài)列表里,并傳遞給下一皇后。 else: for result in queens(num, state+(pos,)): yield (pos, ) + result #result這個變量代表的是quees返回的元組 #若是最后一行 對于 pos in range(num)調(diào)用conflict(state, num) , #如果沒有沖突,生成元組 #若不是最后一行 對于pos in range(num)調(diào)用conflict(state, pos), #如果沒有沖突,state更新,遞歸調(diào)用queens(num, state) state將更新 #為了直觀表現(xiàn)棋盤,用X表示每個皇后的位置 def prettyprint(solution): def line(pos, length=len(solution)): return '. ' * (pos) + 'X ' + '. '*(length-pos-1) for pos in solution: print line(pos) if __name__ == "__main__":#來判斷是否是在直接運行該.py文件 prettyprint(random.choice(list(queens(8))))
運行結(jié)果:
以上是“Python如何解決八皇后問題”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。