復雜度可能高了點- - 也沒太注意
我想了好久 也找了好久 沒看到什么能夠用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+1n :
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皇后內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- python 使用遞歸回溯完美解決八皇后的問題
- Python八皇后問題解答過程詳解
- Python實現八皇后問題示例代碼
- python八皇后問題的解決方法
- Python基于生成器迭代實現的八皇后問題示例
- Python解決八皇后問題示例
- python基于右遞歸解決八皇后問題的方法
