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