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

复杂度可能高了点- - 也没太注意

我想了好久也找了好久没看到什么能够用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皇后内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/skrrrr__/article/details/114829636

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

相关文章

热门资讯