第 21 站 · 回溯

约束搜索与剪枝

N 皇后：按列和两条对角线剪枝最坏 O(n!)

周赛难度分难度分 1720–难度分 1882· 中位难度分 1801（2/8 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 21 站 · 8 题

先学: 回溯枚举
学完去: 没有后续站依赖它。
面试频次: 8 家公司考过 · 面经出现 10 次TikTok / ByteDance 3、Confluent 1、Glean 1、Meta 1、PayPal 1

先做这道

LC 79单词搜索中等

卡住再看

在网格上回溯匹配单词，禁止一条路径重复使用同一格子。

要点

每行只放一个皇后，搜索树只在列上分叉；列、主对角线 r-c、副对角线 r+c 各用一个数组标记。
剪枝越早越好：递归之前就判断冲突，而不是放满整个棋盘再检查。
数独、组合总和这类题先排序，在「剩下的值已经不可能满足」时用 break，比 continue 省得多。

易错点

主对角线下标 r-c 会是负数，要加上 n-1 的偏移。
回溯返回前忘了把标记改回去，后面的分支全被误剪。
需要输出棋盘时，用可变的字符数组逐格修改，最后再转字符串，不要每一步都复制整盘。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

N 皇后 · 按列和对角线剪枝

4 皇后有多少种摆法？

换个输入

·0,0

·0,1

·0,2

·0,3

·1,0

·1,1

·1,2

·1,3

·2,0

·2,1

·2,2

·2,3

·3,0

·3,1

·3,2

·3,3

当前处理已发现 / 已计算答案

已放皇后: 0 / 4
占用的列: —
↘ 对角线 r−c: —
↙ 对角线 r+c: —
解的个数: 0

在 4×4 棋盘上一行放一个皇后。用三个集合记下占用的列和两条对角线，O(1) 判断能不能放。

速度

步骤 1 / 40

始终成立同一条 ↘ 对角线上 r − c 相同，同一条 ↙ 对角线上 r + c 相同；集合里没有才能放。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 79。

Python

def total_queens(n: int) -> int:
    """Number of ways to place n non-attacking queens on an n x n board."""
    cols, diag, anti = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)

    def place(r: int) -> int:
        if r == n:
            return 1
        count = 0
        for c in range(n):
            d = r - c + n - 1  # shift r - c into 0..2n-2
            if cols[c] or diag[d] or anti[r + c]:
                continue  # attacked: prune this branch
            cols[c] = diag[d] = anti[r + c] = True
            count += place(r + 1)
            cols[c] = diag[d] = anti[r + c] = False  # undo
        return count

    return place(0)

C++

// Number of ways to place n non-attacking queens on an n x n board.
int totalQueens(int n) {
    vector<bool> cols(n), diag(2 * n - 1), anti(2 * n - 1);
    function<int(int)> place = [&](int r) {
        if (r == n) return 1;
        int count = 0;
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1;  // shift r - c into 0..2n-2
            if (cols[c] || diag[d] || anti[r + c]) continue;  // attacked: prune this branch
            cols[c] = diag[d] = anti[r + c] = true;
            count += place(r + 1);
            cols[c] = diag[d] = anti[r + c] = false;  // undo
        }
        return count;
    };
    return place(0);
}

Java

class Solution {
    private boolean[] cols, diag, anti;
    private int n;

    // Number of ways to place n non-attacking queens on an n x n board.
    int totalQueens(int n) {
        this.n = n;
        cols = new boolean[n];
        diag = new boolean[2 * n - 1];
        anti = new boolean[2 * n - 1];
        return place(0);
    }

    private int place(int r) {
        if (r == n) return 1;
        int count = 0;
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1; // shift r - c into 0..2n-2
            if (cols[c] || diag[d] || anti[r + c]) continue; // attacked: prune this branch
            cols[c] = diag[d] = anti[r + c] = true;
            count += place(r + 1);
            cols[c] = diag[d] = anti[r + c] = false; // undo
        }
        return count;
    }
}

// totalQueens returns the number of ways to place n non-attacking queens on an n x n board.
func totalQueens(n int) int {
	cols, diag, anti := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
	var place func(r int) int
	place = func(r int) int {
		if r == n {
			return 1
		}
		count := 0
		for c := 0; c < n; c++ {
			d := r - c + n - 1 // shift r - c into 0..2n-2
			if cols[c] || diag[d] || anti[r+c] {
				continue // attacked: prune this branch
			}
			cols[c], diag[d], anti[r+c] = true, true, true
			count += place(r + 1)
			cols[c], diag[d], anti[r+c] = false, false, false // undo
		}
		return count
	}
	return place(0)
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

网格回溯：原地标记，回来再还原时间 O(rows × cols × 3^L) · 递归深度 O(L)

在网格里找一条路径拼出单词、每格最多用一次：从每个格子出发 DFS，当前格先改成占位符表示「这条路已用」，四个方向试完再改回来，不必另开 visited 数组。LC 79 单词搜索；LC 212 单词搜索 II 把单词换成字典树一起找。

Python

def exist(board: list[list[str]], word: str) -> bool:
    """Is word spelled by a path of side-adjacent cells, each used at most once? (LC 79)"""
    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int, k: int) -> bool:  # does board[r][c] start word[k:]?
        if board[r][c] != word[k]:
            return False
        if k == len(word) - 1:
            return True
        board[r][c] = "#"  # used on this path
        found = any(
            0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, k + 1)
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1))
        )
        board[r][c] = word[k]  # restore on the way back
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

C++

// Is word spelled by a path of side-adjacent cells, each used at most once? (LC 79)
bool exist(vector<string> board, const string& word) {
    int rows = board.size(), cols = board[0].size();
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) {  // does board[r][c] start word[k..]?
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[k]) return false;
        if (k == (int)word.size() - 1) return true;
        board[r][c] = '#';  // used on this path
        bool found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        board[r][c] = word[k];  // restore on the way back
        return found;
    };
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (dfs(r, c, 0)) return true;
    return false;
}

Java

class Solution {
    private char[][] board;
    private String word;

    // Is word spelled by a path of side-adjacent cells, each used at most once? (LC 79)
    boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                if (dfs(r, c, 0)) return true;
        return false;
    }

    // Does board[r][c] start word[k..]?
    private boolean dfs(int r, int c, int k) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;
        board[r][c] = '#'; // used on this path
        boolean found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        board[r][c] = word.charAt(k); // restore on the way back
        return found;
    }
}

// exist reports whether word is spelled by a path of side-adjacent cells, each used at most once (LC 79).
func exist(board [][]byte, word string) bool {
	rows, cols := len(board), len(board[0])
	var dfs func(r, c, k int) bool // does board[r][c] start word[k:]?
	dfs = func(r, c, k int) bool {
		if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[k] {
			return false
		}
		if k == len(word)-1 {
			return true
		}
		board[r][c] = '#' // used on this path
		found := dfs(r+1, c, k+1) || dfs(r-1, c, k+1) || dfs(r, c+1, k+1) || dfs(r, c-1, k+1)
		board[r][c] = word[k] // restore on the way back
		return found
	}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if dfs(r, c, 0) {
				return true
			}
		}
	}
	return false
}

数独：行、列、宫各用一个位掩码最坏指数级；常见题面很快 · 空间 O(81)

约束满足类的填格子题（数独、八数码、24 点的变形）：把每行、每列、每宫已用的数字记成位掩码，判断「能不能放 d」只要一次与运算；按空格顺序回溯，放下时置位，退回时清位。LC 37 解数独、LC 36 有效的数独用的是同一组掩码。

Python

def solve_sudoku(board: list[list[str]]) -> bool:
    """Fill the '.' cells in place so each row, column and 3x3 box holds 1-9 once (LC 37)."""
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9  # bit d set: digit d is used there
    empty = []
    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                empty.append((r, c))
            else:
                bit = 1 << int(board[r][c])
                rows[r] |= bit
                cols[c] |= bit
                boxes[r // 3 * 3 + c // 3] |= bit

    def fill(k: int) -> bool:
        if k == len(empty):
            return True
        r, c = empty[k]
        b = r // 3 * 3 + c // 3
        for d in range(1, 10):
            bit = 1 << d
            if (rows[r] | cols[c] | boxes[b]) & bit:
                continue  # d is already in this row, column or box
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
            board[r][c] = str(d)
            if fill(k + 1):
                return True
            rows[r] ^= bit  # undo
            cols[c] ^= bit
            boxes[b] ^= bit
        board[r][c] = "."
        return False

    return fill(0)

C++

// Fill the '.' cells in place so each row, column and 3x3 box holds 1-9 once (LC 37).
bool solveSudoku(vector<string>& board) {
    int rows[9] = {}, cols[9] = {}, boxes[9] = {};  // bit d set: digit d is used there
    vector<pair<int, int>> empty;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                empty.push_back({r, c});
                continue;
            }
            int bit = 1 << (board[r][c] - '0');
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[r / 3 * 3 + c / 3] |= bit;
        }
    function<bool(size_t)> fill = [&](size_t k) {
        if (k == empty.size()) return true;
        auto [r, c] = empty[k];
        int b = r / 3 * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            int bit = 1 << d;
            if ((rows[r] | cols[c] | boxes[b]) & bit) continue;  // d is already in this row, column or box
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[b] |= bit;
            board[r][c] = char('0' + d);
            if (fill(k + 1)) return true;
            rows[r] ^= bit;  // undo
            cols[c] ^= bit;
            boxes[b] ^= bit;
        }
        board[r][c] = '.';
        return false;
    };
    return fill(0);
}

Java

class Solution {
    private final int[] rows = new int[9], cols = new int[9], boxes = new int[9]; // bit d set: digit d is used there
    private final List<int[]> empty = new ArrayList<>();
    private char[][] board;

    // Fill the '.' cells in place so each row, column and 3x3 box holds 1-9 once (LC 37).
    boolean solveSudoku(char[][] board) {
        this.board = board;
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    empty.add(new int[] {r, c});
                    continue;
                }
                int bit = 1 << (board[r][c] - '0');
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[r / 3 * 3 + c / 3] |= bit;
            }
        return fill(0);
    }

    private boolean fill(int k) {
        if (k == empty.size()) return true;
        int r = empty.get(k)[0], c = empty.get(k)[1], b = r / 3 * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            int bit = 1 << d;
            if (((rows[r] | cols[c] | boxes[b]) & bit) != 0) continue; // d is already in this row, column or box
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[b] |= bit;
            board[r][c] = (char) ('0' + d);
            if (fill(k + 1)) return true;
            rows[r] ^= bit; // undo
            cols[c] ^= bit;
            boxes[b] ^= bit;
        }
        board[r][c] = '.';
        return false;
    }
}

// solveSudoku fills the '.' cells in place so each row, column and 3x3 box holds 1-9 once (LC 37).
func solveSudoku(board [][]byte) bool {
	var rows, cols, boxes [9]int // bit d set: digit d is used there
	var empty [][2]int
	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if board[r][c] == '.' {
				empty = append(empty, [2]int{r, c})
				continue
			}
			bit := 1 << (board[r][c] - '0')
			rows[r] |= bit
			cols[c] |= bit
			boxes[r/3*3+c/3] |= bit
		}
	}
	var fill func(k int) bool
	fill = func(k int) bool {
		if k == len(empty) {
			return true
		}
		r, c := empty[k][0], empty[k][1]
		b := r/3*3 + c/3
		for d := 1; d <= 9; d++ {
			bit := 1 << d
			if (rows[r]|cols[c]|boxes[b])&bit != 0 {
				continue // d is already in this row, column or box
			}
			rows[r] |= bit
			cols[c] |= bit
			boxes[b] |= bit
			board[r][c] = byte('0' + d)
			if fill(k + 1) {
				return true
			}
			rows[r] ^= bit // undo
			cols[c] ^= bit
			boxes[b] ^= bit
		}
		board[r][c] = '.'
		return false
	}
	return fill(0)
}

为什么对

每行恰好放一个皇后不会漏解：任何合法摆法里 n 个皇后两两不同行，所以必然每行一个，按行搜索只是固定了枚举顺序。
同一条主对角线上 r − c 相同，同一条副对角线上 r + c 相同，所以三个布尔数组就能 O(1) 判断冲突。
剪枝是安全的：被剪掉的部分摆法已经有冲突，继续往下放只会保留这个冲突，不可能变成合法解。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

N 皇后我按行回溯，每行放一个，只在列上分支。用三个数组分别标记列、主对角线 r − c 和副对角线 r + c，放之前 O(1) 检查冲突，有冲突就不递归，越早剪越好。之所以安全，是因为已经冲突的部分摆法再怎么往下放都不会变合法。数独、组合总和也一样，先排序，后面不可能满足就直接 break。

English

For N-Queens I backtrack row by row, one queen per row, branching only on the column. Three arrays mark used columns, diagonals r − c and anti-diagonals r + c, so I check a conflict in O(1) before recursing and prune as early as possible. That is safe because a partial board with a conflict can never become valid by adding queens. Sudoku and combination sum work the same way: sort first and break as soon as the rest cannot fit.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

每行恰好放一个皇后不会漏解：任何合法摆法里 n 个皇后两两不同行，所以必然每行一个，按行搜索只是固定了枚举顺序。
同一条主对角线上 r − c 相同，同一条副对角线上 r + c 相同，所以三个布尔数组就能 O(1) 判断冲突。
剪枝是安全的：被剪掉的部分摆法已经有冲突，继续往下放只会保留这个冲突，不可能变成合法解。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

def total_queens(n: int) -> int:
    """Number of ways to place n non-attacking queens on an n x n board."""
    cols, diag, anti = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)


    return place(0)

分档练习

本站在 500 路里的 8 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 4

#	题目	一句话思路	难度分
79	单词搜索	在网格上回溯匹配单词，禁止一条路径重复使用同一格子。
51	N 皇后	逐行放置皇后，用列和两类对角线冲突进行剪枝。
52	N 皇后 II	把输出方案改为计数，练习无结果存储的约束搜索。
1239	串联字符串的最大长度	在字符串选择过程中维护已用字符，发现冲突立即剪枝。	难度分 1720

进阶 4

#	题目	一句话思路	难度分
212	单词搜索 II	将多单词匹配与前缀树剪枝结合，避免为每个单词重复遍历网格。
37	解数独	维护行、列、宫约束求解数独，优先选择候选最少的位置。
679	24 点游戏	每次合并两个数枚举运算，覆盖不同括号结构并处理数值比较。
1255	得分最高的单词集合	回溯选择单词并扣减字母库存，在资源约束下最大化得分。	难度分 1882

先做这道

要点

易错点

看动画

模板

常见变体

为什么对

30 秒口述稿

自评一下

小测

模板练习

分档练习

核心 4

进阶 4