k×k棋盘放置N皇后的全解算法咨询及DFS优化需求

原代码的问题分析 #

你的DFS代码本质是标准N皇后（n×n棋盘放n个皇后）的实现：用queen数组的索引代表皇后所在的行，数组值代表列。这就导致你只能在前queen_number行依次放置皇后，无法在k×k棋盘的任意行中选择位置放置N个皇后——这是核心局限。

修正后的DFS实现 #

要解决这个问题，需要同时追踪每个皇后的行和列，而非默认行是数组索引。具体优化点：

• 用集合记录已占用的行，避免重复放置
• 用两个集合分别记录主对角线（行-列为定值）和副对角线（行+列为定值），将冲突判断从O(n)降到O(1)
• 递归时遍历所有未被占用的行，尝试在该行的每一列放置皇后

修正后的代码示例：

def find_all_n_queens_on_k_board(k, n):
    ret = []
    # 已占用的行、主对角线(row-col)、副对角线(row+col)
    used_rows = set()
    main_diag = set()
    anti_diag = set()
    
    def dfs(current_queens):
        if len(current_queens) == n:
            ret.append(current_queens.copy())
            return
        
        # 遍历所有未被占用的行
        for row in range(k):
            if row in used_rows:
                continue
            # 遍历当前行的所有列
            for col in range(k):
                md = row - col
                ad = row + col
                if md in main_diag or ad in anti_diag:
                    continue
                # 放置皇后并回溯
                used_rows.add(row)
                main_diag.add(md)
                anti_diag.add(ad)
                current_queens.append((row, col))
                dfs(current_queens)
                current_queens.pop()
                anti_diag.remove(ad)
                main_diag.remove(md)
                used_rows.remove(row)
    
    dfs([])
    return ret

更优的实现思路 #

1. 位运算剪枝（行选择优化） #

如果k≤32，可以用整数二进制位表示已占用的行，将行占用判断从集合操作的O(1)优化为位运算的O(1)，速度更快：

• used_rows_bitmask：二进制位为1的位置代表该行已被占用
• 可用行通过~used_rows_bitmask & ((1 << k) - 1)直接获取位掩码，再遍历其中为1的位对应行

2. 提前剪枝减少无效递归 #

递归前判断剩余需放置的皇后数量是否≤剩余可用行数量，不满足则直接返回：

remaining = n - len(current_queens)
available_rows = k - len(used_rows)
if remaining > available_rows:
    return

3. 棋盘可视化扩展 #

如果需要将结果转换为直观的棋盘格式，可以添加格式化函数：

def format_board(queens, k):
    board = [['.' for _ in range(k)] for _ in range(k)]
    for row, col in queens:
        board[row][col] = 'Q'
    return [''.join(row) for row in board]

# 使用示例
solutions = find_all_n_queens_on_k_board(5, 3)
for idx, sol in enumerate(solutions):
    print(f"Solution {idx+1}:")
    for line in format_board(sol, 5):
        print(line)
    print()

内容的提问来源于stack exchange，提问作者Q Chen