python 非遞歸解決n皇後問題的方法
復雜度可能高瞭點- – 也沒太註意
我想瞭好久 也找瞭好久 沒看到什麼能夠用python解決n皇後問題而且不調用遞歸的 因為我不太能理解遞歸(尤其是到n層時) 智商受限- –
import copy def check(A,x,y): B=[] flag=True for i in range(len(A)): for j in range(len(A)): if A[i][j]==1: B.append([i,j]) for m in range(len(B)): p = B[m][0] q = B[m][1] if y == q or (x-p)==abs(y-q): flag=False return flag def queen(n): A=[[0 for __ in range(n)] for _ in range(n)] answer=[] for _ in range(n): stack=[[0,_,A]] while stack: judge = 0 obj=stack.pop(-1) x=obj[0] y=obj[1] array=obj[2] flag=check(array,x,y) if not flag: while 1: if check(array, x, y): break else: if stack: b=stack.pop(-1) x=b[0] y=b[1] array=b[2] else: judge=1 break if judge==1: break array=copy.deepcopy(array) array[x][y]=1 for m in range(n): if m!=y and m!=y-1 and m!=y+1 and x+1<n : stack.append([x+1,m,array]) # print(array) for j in range(len(array[n-1])): if array[n-1][j]==1: answer.append(array) print(len(answer)) queen(8)
answer中存放的就是最後所有的可行組合
當前解決的是8皇後問題
我的想法是用dfs 在每次搜索時 帶上該次搜索需要擺放的位置 x,y,以及待擺放的棋盤 即[x,y,A]
這樣不會導致所有的操作都在一個矩陣上進行
到此這篇關於python 非遞歸解決n皇後問題的方法的文章就介紹到這瞭,更多相關python 非遞歸n皇後內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Python真題案例之小學算術 階乘精確值 孿生素數 6174問題詳解
- python numpy.power()數組元素求n次方案例
- 7個關於Python的經典基礎案例
- Python真題案例之蛇形數組詳解
- Python中的復雜數據類型(list、tuple)