DSA Interview Prep · 课时

N 皇后与约束传播

Q: 「N 皇后与约束传播」课时是免费的吗？

是的 — 「N 皇后与约束传播」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

Q: 「N 皇后与约束传播」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用列集合和对角线集合在 O(1) 时间内检查约束，将 N 个皇后放置在 N×N 棋盘上，并讨论如何统计解的数量与枚举解。

N 皇后与约束传播 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

N 皇后问题

N 皇后问题（LeetCode 51/52）要求您在 N×N 的棋盘上放置 N 个皇后，使任意两个皇后都无法相互攻击。皇后可以沿行、列以及两条对角线攻击。对于 N=4，恰好有 2 个解。对于 N=8（经典版本），有 92 个解。这是最经典的回溯问题，通过检查约束可以大幅剪枝搜索空间。

# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)

# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)

每行放置一个皇后

由于任意两个皇后不能位于同一行，我们在每行恰好放置一个皇后。回溯按行递归，为每一行选择一列。这样就把每个皇后 N² 个选择的搜索空间减少为每行只有 N 列，形成 N^N 个初始分支——但约束会大幅减少实际搜索量。递归深度为 N（每行一层），分支因子最多为 N。

def solve_n_queens(n):
    results = []
    queens = []  # queens[row] = column of queen in that row
    
    def backtrack(row):
        if row == n:
            # Build the board representation
            board = []
            for r in range(n):
                board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
            results.append(board)
            return
        for col in range(n):
            if is_valid(row, col):
                queens.append(col)   # CHOOSE
                backtrack(row + 1)   # EXPLORE
                queens.pop()         # UNCHOOSE
    
    def is_valid(row, col):
        for r, c in enumerate(queens):
            if c == col: return False             # same column
            if abs(row - r) == abs(col - c): return False  # diagonal
        return True
    
    backtrack(0)
    return results

print(len(solve_n_queens(4)), 'solutions for N=4')  # 2
print(len(solve_n_queens(8)), 'solutions for N=8')  # 92

使用集合进行 O(1) 约束检查

通过扫描所有已放置的皇后来检查有效性时，每个候选项需要 O(N) 的时间，最坏情况下整个算法为 O(N² × N!)。通过维护三个集合，可以将每次有效性检查降为 O(1)：cols（已占用的列）、diag（左上到右下对角线的行−列值）和 anti_diag（右上到左下对角线的行+列值）。位于同一条对角线上的皇后具有相同的行−列值；位于同一条反对角线上的皇后具有相同的行+列值。

def solve_n_queens_fast(n):
    results = []
    cols = set()       # occupied columns
    diag = set()       # row - col (positive diagonal)
    anti = set()       # row + col (negative diagonal)
    queens = []
    
    def backtrack(row):
        if row == n:
            board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
            results.append(board)
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue  # PRUNE: constraint violated
            # CHOOSE
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            backtrack(row + 1)  # EXPLORE
            # UNCHOOSE
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    
    backtrack(0)
    return results

print(len(solve_n_queens_fast(8)))  # 92

对角线不变量详解

对角线的关键规律是：同一条从左上到右下的对角线上的所有单元格，都具有相同的 row - col 值。例如，(0,0)、(1,1)、(2,2) 的 row-col=0。所有位于同一条反对角线上的单元格，都具有相同的 row + col 值：(0,2)、(1,1)、(2,0) 的 row+col=2。这些常数时间不变量让我们可以通过 O(1) 的集合查找来检查对角线冲突，而不必进行 O(N) 的线性扫描。

# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
    print([r-c for c in range(n)])

print('row+col values (same anti-diagonal):')
for r in range(n):
    print([r+c for c in range(n)])

# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2)  # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0)  # both 2

统计解的数量：N 皇后 II

N 皇后 II（LeetCode 52）只要求返回解的数量，而不是棋盘布局。这允许进行小幅优化：跳过棋盘构造步骤，只需递增计数器。使用位掩码代替集合，还可以将每次操作的速度进一步提升到接近 O(1)。解的数量并不单调增长：1(N=1)、0(N=2)、0(N=3)、2(N=4)、10(N=5)、4(N=6)、40(N=7)、92(N=8)。

def total_n_queens(n):
    count = [0]
    cols = set(); diag = set(); anti = set()
    def backtrack(row):
        if row == n:
            count[0] += 1
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            backtrack(row + 1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col)
    backtrack(0)
    return count[0]

for n in range(1, 11):
    print(f'N={n}: {total_n_queens(n)} solutions')

使用位掩码加速 N 皇后

对于非常大的 N，位掩码实现的运行速度会明显更快。使用三个整数作为位掩码：cols、left_diag（每行向左移位）和 right_diag（每行向右移位）。可用列为 ((1<<n)-1) & ~(cols|left_diag|right_diag)。使用 bit = available & -available 提取每个可用列（最低位的置位比特），然后进行递归。通过位运算，这种方法可以将每次约束检查的复杂度降为 O(1)。

def total_n_queens_bitmask(n):
    full = (1 << n) - 1  # all n columns set
    count = [0]
    def bt(cols, left_diag, right_diag):
        if cols == full:
            count[0] += 1
            return
        available = full & ~(cols | left_diag | right_diag)
        while available:
            bit = available & -available  # lowest set bit
            available &= available - 1   # remove lowest bit
            bt(cols | bit,
               (left_diag | bit) << 1,
               (right_diag | bit) >> 1)
    bt(0, 0, 0)
    return count[0]

for n in range(1, 13):
    print(f'N={n}: {total_n_queens_bitmask(n)}')

约束传播概念

约束传播 不只是简单的剪枝：放置一个皇后后，立即推导并排除未来各行中的所有无效位置。这比检查每个候选项的有效性更加积极——您会在进行分支前主动缩小搜索空间。最著名的例子是 SAT 求解器和数独求解器中的弧一致性：放置一个数字后，会排除同一行、同一列和同一个 3×3 宫中的其他选项。

# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further

# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
    cols = set(q for q in queens)
    diags = set(r - q for r, q in enumerate(queens))
    anti_diags = set(r + q for r, q in enumerate(queens))
    row = len(queens)
    return [c for c in range(n)
            if c not in cols
            and (row-c) not in diags
            and (row+c) not in anti_diags]

print(remaining_columns(8, [0]))  # valid cols for row 1 after placing col 0 in row 0

数独求解器

数独是约束传播问题的典型代表。在每个空单元格中，有效数字选项必须是同一行、同一列或同一个 3×3 宫中尚未出现的数字。回溯求解器的步骤是：找到第一个空单元格，尝试每个有效数字，然后递归求解。如果遇到矛盾（空单元格中没有任何有效数字），就回溯。优秀的数独求解器还会在回溯前应用约束传播（候选数标记）。

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num: return False  # row
            if board[i][c] == num: return False  # col
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                if board[br+i][bc+j] == num: return False  # box
        return True
    
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for d in '123456789':
                        if is_valid(r, c, d):
                            board[r][c] = d
                            if backtrack(): return True
                            board[r][c] = '.'
                    return False  # no valid digit found
        return True  # no empty cells: solved
    
    backtrack()
    return board

# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')

最受约束变量启发式方法

这是约束满足问题的一项关键优化：始终优先选择受约束最多的变量（有效选项最少的单元格）。在数独中，如果某个单元格只有 1 个有效数字，那么立即填入它是必然的选择——无需回溯。优先选择这类单元格可以显著降低搜索树的深度。这就是人工智能约束编程中的最小剩余值（MRV）启发式方法。

def solve_sudoku_mrv(board):
    '''Find cell with fewest valid choices (MRV heuristic).'''
    def valid_choices(r, c):
        nums = set('123456789')
        for i in range(9):
            nums.discard(board[r][i])
            nums.discard(board[i][c])
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                nums.discard(board[br+i][bc+j])
        return nums
    
    def find_mrv():
        best = (10, -1, -1, set())  # (choices_count, r, c, choices)
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    choices = valid_choices(r, c)
                    if len(choices) < best[0]:
                        best = (len(choices), r, c, choices)
        return best[1], best[2], best[3]
    
    def backtrack():
        r, c, choices = find_mrv()
        if r == -1: return True  # no empty cells
        for d in choices:
            board[r][c] = d
            if backtrack(): return True
            board[r][c] = '.'
        return False
    
    backtrack()
    return board

N 皇后解数量表

N 皇后的解数量遵循以下著名序列：N=1：1，N=2：0，N=3：0，N=4：2，N=5：10，N=6：4，N=7：40，N=8：92，N=9：352，N=10：724。目前尚未发现闭式公式；必须通过计算得到数量。对于 N=27，大约存在 2.34 × 10^17 个解。面试题通常要求 N ≤ 9。理解这种指数级增长，有助于说明为什么对于较大的 N，位掩码优化非常重要。

def count_queens(n):
    '''O(1) per constraint check using sets.'''
    count = [0]
    cols = set(); diag = set(); anti = set()
    def bt(row):
        if row == n: count[0] += 1; return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            bt(row+1)
            cols.discard(col); diag.discard(row-col); anti.discard(row+col)
    bt(0)
    return count[0]

sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]

N 皇后棋盘构造

当面试官要求返回实际棋盘（LeetCode 51）时，请根据 queens 列表构造每个棋盘，其中 queens[r] 表示第 r 行中皇后的列。字符串构造方式是：对每一行使用 '.' * col + 'Q' + '.' * (n - col - 1)。这种 O(n²) 的构造只会在递归树的叶节点处调用（即所有 N 个皇后都已放置），因此不会影响总体复杂度。

def n_queens_boards(n):
    results = []
    queens = []
    cols = set(); diag = set(); anti = set()
    def build_board():
        return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
    def bt(row):
        if row == n:
            results.append(build_board())
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            bt(row+1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    bt(0)
    return results

for board in n_queens_boards(4):
    for row in board: print(row)
    print()

快速检查

测试您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学习了：N 皇后问题每行放置一个皇后，并使用集合记录列、对角线（行-列）和副对角线（行+列），从而以 O(1) 检查约束；位掩码可以进一步加速约束检查，使探索所有放置方案时每次操作的开销接近 O(1)；以及约束传播（MRV 启发式方法）通过始终优先选择受约束最多的变量来减少搜索。接下来，我们将比较贪心与 DP 方法，并学习何时应用其中一种。

常见问题解答