Python实现非递归N皇后问题：基于DFS栈模拟的解决方案

小石头

发布时间：2026-10-14| 3人浏览过

原创

本文介绍一种在Python中不使用递归解决N皇后问题的方法。通过深度优先搜索（DFS）结合显式栈结构，模拟递归过程，每次搜索携带位置坐标与棋盘状态，有效避免深层递归带来的理解困难与栈溢出风险。代码以8皇后为例，展示完整实现逻辑与结果输出。

非递归N皇后问题的实现思路

该方案的计算复杂度可能偏高，且作者在实现过程中未对性能进行充分优化。

经过长时间搜索，未发现其他使用Python实现且完全避免递归调用的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)