回溯进阶：N 皇后与数独

N 皇后问题

问题：在 n×n 棋盘上放置 n 个皇后，要求任意两个皇后不能同行、同列、同对角线。返回所有合法方案。

解题思路

逐行放置，每行选一列，用三个集合记录已占用的列、左对角线、右对角线。

• 左对角线：同一左斜线上的格子，row - col 相同
• 右对角线：同一右斜线上的格子，row + col 相同

List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];  // queens[row] = col：第 row 行皇后放在第 col 列
    Arrays.fill(queens, -1);
    Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
    backtrack(n, 0, queens, cols, diag1, diag2, res);
    return res;
}

void backtrack(int n, int row, int[] queens,
               Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
               List<List<String>> res) {
    if (row == n) {
        res.add(buildBoard(queens, n));
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) {
            continue;  // 剪枝：此列已被占用
        }
        queens[row] = col;
        cols.add(col);
        diag1.add(row - col);
        diag2.add(row + col);
        backtrack(n, row + 1, queens, cols, diag1, diag2, res);
        queens[row] = -1;
        cols.remove(col);
        diag1.remove(row - col);
        diag2.remove(row + col);
    }
}

List<String> buildBoard(int[] queens, int n) {
    List<String> board = new ArrayList<>();
    for (int row = 0; row < n; row++) {
        char[] line = new char[n];
        Arrays.fill(line, '.');
        line[queens[row]] = 'Q';
        board.add(new String(line));
    }
    return board;
}

时间：O(N!)（最坏情况），空间：O(N)（queens 数组 + 递归栈）。

位运算优化（可选进阶）

用位运算代替 HashSet，速度更快：

void solve(int n, int row, int cols, int diag1, int diag2, List<List<String>> res, int[] queens) {
    if (row == n) { res.add(buildBoard(queens, n)); return; }
    int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);  // 可用列的位掩码
    while (available != 0) {
        int pos = available & (-available);  // 取最低位的1（最低可用列）
        available &= available - 1;          // 清除最低位
        int col = Integer.numberOfTrailingZeros(pos);
        queens[row] = col;
        solve(n, row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1, res, queens);
    }
}

解数独

问题：填充 9×9 数独，使每行、每列、每个 3×3 小方格中数字 1-9 均只出现一次。

解题思路

逐格填充，遇到空格尝试 1-9，满足约束则继续，否则回溯。

void solveSudoku(char[][] board) {
    backtrack(board);
}

boolean backtrack(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;  // 跳过已填格
            for (char num = '1'; num <= '9'; num++) {
                if (!isValid(board, r, c, num)) continue;
                board[r][c] = num;
                if (backtrack(board)) return true;  // 找到解直接返回
                board[r][c] = '.';  // 回溯
            }
            return false;  // 1-9 都不行，返回 false（触发上层回溯）
        }
    }
    return true;  // 所有格子都填完了
}

boolean isValid(char[][] board, int r, int c, char num) {
    for (int i = 0; i < 9; i++) {
        if (board[r][i] == num) return false;           // 同行
        if (board[i][c] == num) return false;           // 同列
        int boxR = (r / 3) * 3 + i / 3;
        int boxC = (c / 3) * 3 + i % 3;
        if (board[boxR][boxC] == num) return false;    // 同 3×3 方格
    }
    return true;
}

进阶优化

• 位掩码：用 int[9] 存每行/列/方格的已用数字位图，O(1) 校验
• 最少候选值优先（MRV启发）：从候选最少的空格开始填，减少无效搜索

单词搜索

在字母矩阵中，查找是否存在从任一位置出发的、沿上下左右连续相邻格子拼出的目标单词。

boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, r, c, 0)) return true;
        }
    }
    return false;
}

boolean dfs(char[][] board, String word, int r, int c, int idx) {
    if (idx == word.length()) return true;
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(idx)) return false;
    char tmp = board[r][c];
    board[r][c] = '#';  // 标记已访问（防止重复使用）
    boolean found = dfs(board, word, r+1, c, idx+1)
                 || dfs(board, word, r-1, c, idx+1)
                 || dfs(board, word, r, c+1, idx+1)
                 || dfs(board, word, r, c-1, idx+1);
    board[r][c] = tmp;  // 恢复
    return found;
}

回溯剪枝总结

回溯的本质：在决策树上深度优先搜索，通过剪枝减少不必要的分支。