N皇后问题递归实现故障排查及修正请求（board_shape>5时失效）

问题背景 #

N皇后问题是计算机科学专业递归章节最早教授的问题之一，在数学和计算机领域均有深入研究。我采用深度优先搜索（DFS）方式编写了该问题的代码，期望获取N×N棋盘上N个皇后的合法位置列表。

原代码如下：

import copy

# At some point, I thought recursion limit was the problem, but I don't think so.
# import sys
# sys.setrecursionlimit(1_000_000_000)
board_shape = 9
queen_moves = list()


def check_collision(var_current, var_others):
    if len(var_others) > 0:
        for queens in var_others:
            if var_current[0] == queens[0]:
                return True
            elif var_current[1] == queens[1]:
                return True
            elif abs(var_current[0] - queens[0]) == abs(var_current[1] - queens[1]) :
                return True

    return False


def n_queen(pos_X, pos_Y, queens_t, total_queens):
    if pos_X > -1 and pos_X < board_shape:
        if pos_Y > -1 and pos_Y < board_shape and queens_t < board_shape:

            current_queen = [pos_X, pos_Y, queens_t + 1]
            copy_of_moves = copy.deepcopy(total_queens)

            if check_collision(current_queen, copy_of_moves) is False:
                copy_of_moves.append(current_queen)
                print(copy_of_moves, "\t", len(copy_of_moves))
            else:
                return

            if len(copy_of_moves) == board_shape :
                print("There is a route")
                print(copy_of_moves)
                return

            n_queen(pos_X=pos_X + 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X + 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)

            n_queen(pos_X=pos_X + 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X + 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)

if __name__ == "__main__":
    moves = list()
    # Thought I would get at least one result if I go through all the rows or columns but no luck.
    for i in range(board_shape):
        n_queen(i, 0, 0, moves)

我尝试用递归解决N皇后问题，该算法在board_shape≤5时运行正常，但当输入值大于5时，递归仅能进行到深度5，无法继续推进。若可能，请指出导致问题的代码部分，并提供修正后的代码。

问题分析 #

1. 移动逻辑完全错误：原代码递归调用时仅尝试了8种类似“马走日”的移动方式，这不符合N皇后的规则——N皇后允许在任意合法位置放置皇后，只要不同行、列、对角线即可，这种限制移动步长的逻辑会导致大部分棋盘位置无法被遍历，当N>5时，根本无法找到足够的合法位置。
2. 回溯逻辑缺失：原代码在遇到冲突时直接返回，没有回溯到上一步尝试其他位置；找到一个解后也直接返回，无法继续寻找其他可能的解。
3. 低效的深拷贝：每次递归都深拷贝皇后列表，虽然避免了引用问题，但大幅降低了代码效率，其实可以通过回溯法（添加皇后→递归→移除皇后）来避免深拷贝。

修正后的代码 #

board_shape = 9
solutions = []

def is_safe(row, col, queens):
    # 检查列和对角线冲突（行冲突通过逐行放置避免）
    for r, c in queens:
        if col == c or abs(row - r) == abs(col - c):
            return False
    return True

def dfs(row, queens):
    # 递归终止条件：所有行都放置了皇后
    if row == board_shape:
        # 将皇后位置转换为[行, 列, 序号]的格式，和原代码输出一致
        solution = [[r, c, idx+1] for idx, (r, c) in enumerate(queens)]
        solutions.append(solution)
        print("找到一个解：")
        print(solution)
        return
    
    # 遍历当前行的所有列，尝试放置皇后
    for col in range(board_shape):
        if is_safe(row, col, queens):
            # 放置皇后
            queens.append((row, col))
            # 递归处理下一行
            dfs(row + 1, queens)
            # 回溯：移除当前皇后，尝试下一列
            queens.pop()

if __name__ == "__main__":
    dfs(0, [])
    print(f"共找到 {len(solutions)} 个解")

代码说明 #

• 逐行放置：通过row参数控制逐行放置皇后，天然避免了行冲突，减少了冲突检查的复杂度。
• 冲突检查优化：只需要检查列和对角线冲突，无需检查行冲突。
• 回溯逻辑：放置皇后后递归处理下一行，递归结束后移除当前皇后，尝试当前行的下一列，确保遍历所有可能的合法位置。
• 收集所有解：将所有合法的皇后位置组合存入solutions列表，便于后续使用。

内容的提问来源于stack exchange，提问作者Rishabh Joshi