python基于右遞歸解決八皇后問題的方法
更新時(shí)間：2015年05月25日 12:16:42 作者：小蘿莉
這篇文章主要介紹了python基于右遞歸解決八皇后問題的方法,實(shí)例分析了右遞歸算法的相關(guān)使用技巧,需要的朋友可以參考下
本文實(shí)例講述了python基于右遞歸解決八皇后問題的方法。分享給大家供大家參考。具體分析如下：
凡是線性回溯都可以歸結(jié)為右遞歸的形式，也即是二叉樹，因此對(duì)于只要求一個(gè)解的問題，采用右遞歸實(shí)現(xiàn)的程序要比回溯法要優(yōu)美的多。
def Test(queen,n):
'''這個(gè)就不用說了吧，就是檢驗(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):
'''這個(gè)負(fù)責(zé)安置第n（下標(biāo)，0-7）行皇后，每次調(diào)用，皇后都至少會(huì)移動(dòng)一步'''
queen[n]+=1
while queen[n]<8 and not Test(queen,n):queen[n]+=1
return queen[n]<8
def Solve(queen,n):
'''這個(gè)負(fù)責(zé)解決第n（下標(biāo)，0-7）行皇后的安置以及隨后所有皇后的安置'''
if n==8:#安置完所有皇后了，故輸出列表
print queen
return True#如果設(shè)為假，則會(huì)嘗試所有的安置方案
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)闀?huì)初始化
#雖然我們沒有進(jìn)行回溯，但事實(shí)上，我們每一個(gè)參數(shù)相同的Solve函數(shù)都嘗試了多次
#輸出：[0, 4, 7, 5, 2, 6, 1, 3]
#比回溯法容易多了吧
希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
Django?+?Taro?前后端分離項(xiàng)目實(shí)現(xiàn)企業(yè)微信登錄功能
這篇文章主要介紹了Django?+?Taro?前后端分離項(xiàng)目實(shí)現(xiàn)企業(yè)微信登錄功能,本文記錄一下企業(yè)微信登錄的流程,結(jié)合示例代碼給大家分享實(shí)現(xiàn)思路，需要的朋友可以參考下2022-04-04
Python爬蟲抓取技術(shù)的一些經(jīng)驗(yàn)
這篇文章主要介紹了Python爬蟲抓取技術(shù)的一些經(jīng)驗(yàn),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
傅里葉變換是一種函數(shù)在空間域和頻率域的變換，從空間域到頻率域的變換是傅里葉變換，而從頻率域到空間域是傅里葉的反變換。這篇文章主要為大家介紹的是通過Python實(shí)現(xiàn)圖像的傅里葉變換，感興趣的可以了解一下2021-12-12
Python pandas 重命名索引和列名稱的實(shí)現(xiàn)
本文主要介紹了Python pandas 重命名索引和列名稱的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
編寫Python腳本來獲取Google搜索結(jié)果的示例
這篇文章主要介紹了編寫Python腳本來獲取Google搜索結(jié)果的示例,也是利用Python編寫爬蟲的一個(gè)簡(jiǎn)單實(shí)現(xiàn),需要的朋友可以參考下2015-05-05
用Python PIL實(shí)現(xiàn)幾個(gè)簡(jiǎn)單的圖片特效
這篇文章主要介紹了用Python PIL實(shí)現(xiàn)幾個(gè)簡(jiǎn)單的圖片特效，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-01-01
這篇文章主要為大家詳細(xì)介紹了pygame實(shí)現(xiàn)彈力球及其變速效果，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-07-07
本文講解了python的pandas基本用法，大家可以參考下2018-03-03
策略模式屬于Python-設(shè)計(jì)模式中行為模式之一，該模式定義了一系列算法，并將每個(gè)算法封裝起來，使它們可以相互替換。本文將通過示例詳細(xì)講解這一模式，需要的可以參考一下2023-02-02
Jupyter安裝拓展nbextensions及解決官網(wǎng)下載慢的問題
這篇文章主要介紹了Jupyter安裝拓展nbextensions及解決官網(wǎng)下載慢的問題，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03