欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-09 08:19:22
复杂度可能高了点- - 也没太注意我想了好久 也找了好久 没看到什么能够用python解决n皇后问题而且不调用递归的 因为我不太能理解递归(尤其是到n层时) 智商受限- -import copydef...

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

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