python基于右遞歸解決八皇后問題的方法
更新時間：2015年05月25日 12:16:42 作者：小蘿莉
這篇文章主要介紹了python基于右遞歸解決八皇后問題的方法,實(shí)例分析了右遞歸算法的相關(guān)使用技巧,需要的朋友可以參考下
本文實(shí)例講述了python基于右遞歸解決八皇后問題的方法。分享給大家供大家參考。具體分析如下：
凡是線性回溯都可以歸結(jié)為右遞歸的形式，也即是二叉樹，因此對于只要求一個解的問題，采用右遞歸實(shí)現(xiàn)的程序要比回溯法要優(yōu)美的多。
def Test(queen,n):
'''這個就不用說了吧，就是檢驗(yàn)第n（下標(biāo)，0-7）行皇后的位置是否合理'''
q=queen[n]
for i in xrange(n):
if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i-n:return False
return True
def Settle(queen,n):
'''這個負(fù)責(zé)安置第n（下標(biāo)，0-7）行皇后，每次調(diào)用，皇后都至少會移動一步'''
queen[n]+=1
while queen[n]<8 and not Test(queen,n):queen[n]+=1
return queen[n]<8
def Solve(queen,n):
'''這個負(fù)責(zé)解決第n（下標(biāo)，0-7）行皇后的安置以及隨后所有皇后的安置'''
if n==8:#安置完所有皇后了，故輸出列表
print queen
return True#如果設(shè)為假，則會嘗試所有的安置方案
else:
queen[n]=-1#初始化第n行皇后的起始位置（起始位置-1，可安置在0-7）
while Settle(queen,n):#如果成功安置皇后
if Solve(queen,n+1):#安置其余皇后
return True#成功安置，返回真
return False#失敗，返回假
if __name__=='__main__':
Solve([-1 for i in range(8)],0)#列表的值可以隨便設(shè)置，因?yàn)闀跏蓟?
#雖然我們沒有進(jìn)行回溯，但事實(shí)上，我們每一個參數(shù)相同的Solve函數(shù)都嘗試了多次
#輸出：[0, 4, 7, 5, 2, 6, 1, 3]
#比回溯法容易多了吧
希望本文所述對大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
運(yùn)動檢測ViBe算法python實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了運(yùn)動檢測ViBe算法python實(shí)現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
Python中os.path.join函數(shù)的用法示例詳解
這篇文章主要給大家介紹了關(guān)于Python中os.path.join函數(shù)用法的相關(guān)資料,os.path.join函數(shù)是Python標(biāo)準(zhǔn)庫中的一個函數(shù),用于將多個路徑組合成一個有效的路徑,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-10-10
Python+PyQt5+MySQL實(shí)現(xiàn)天氣管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了Python+PyQt5+MySQL實(shí)現(xiàn)天氣管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-06-06
七夕要來啦,小編在閑暇之余創(chuàng)作了一個基于Python+Turtle的愛心光波表白,文中有詳細(xì)的代碼示例,對我們七夕表白有很大的幫助,感興趣的小伙伴們快來來看看吧2023-08-08
這篇文章主要給大家介紹了關(guān)于Python常見的錯誤以及其解決方案的相關(guān)資料,學(xué)習(xí)python任重而道遠(yuǎn),對于初學(xué)者來說,最難受的就是報(bào)錯,本文總結(jié)了一些常見錯誤,需要的朋友可以參考下2023-08-08
解決Pytorch訓(xùn)練過程中l(wèi)oss不下降的問題
今天小編就為大家分享一篇解決Pytorch訓(xùn)練過程中l(wèi)oss不下降的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
本文介紹Python-Selenium自動化爬蟲,Selenium是一個Web的自動化測試工具，最初是為網(wǎng)站自動化測試而開發(fā)的，Selenium?可以直接運(yùn)行在瀏覽器上,它支持所有主流的瀏覽器,可以接收指令,讓瀏覽器自動加載頁面,獲取需要的數(shù)據(jù),甚至頁面截屏,xiamian?neir?需要的朋友可以參考下2022-01-01
這篇文章主要介紹了python中讓自定義的類使用加號"+",如果對兩個對象直接“+”肯定是不行的，因?yàn)檫€沒有對CartoonImage類重載加法運(yùn)算符__add__(),下文小編舉例形式講解該內(nèi)容，需要的下伙伴可以參考一下2022-03-03
Pandas是一個功能強(qiáng)大且通用的Python庫,用于數(shù)據(jù)操作和分析,它最有用的特性之一是數(shù)據(jù)透視表,它允許您重塑和匯總數(shù)據(jù),但是,使用數(shù)據(jù)透視表通常會導(dǎo)致多級（分層）索引,在本文中,我們將探討如何在Pandas中使用透視表后去掉多級索引,需要的朋友可以參考下2024-12-12
下面小編就為大家分享一篇python3 遍歷刪除特定后綴名文件的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04