网络编程
位置：首页>> 网络编程>> Python编程>> python 非递归解决n皇后问题的方法

python 非递归解决n皇后问题的方法

作者：skrrrr__　　发布时间：2023-07-06 09:38:05　

标签：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]
这样不会导致所有的操作都在一个矩阵上进行

来源：https://blog.csdn.net/skrrrr__/article/details/114829636

0
投稿

猜你喜欢

手机版 网络编程 asp之家 www.aspxhome.com