Day 4：回溯剪枝优化（N皇后、数独）

📖 一、回溯算法简介

回溯算法 是一种通过构造解空间树来进行问题求解的方法。其基本思想是 深度优先搜索（DFS），通过递归遍历所有可能的解，并在每一步选择时进行决策，若当前解不符合要求，则返回上一层进行尝试。

回溯的特点：

• 递归搜索：遍历所有解。
• 剪枝：在搜索过程中，遇到无效或不满足条件的路径时进行回溯。
• 解空间树：每次递归都可以看作是树的一个分支。

---

📌 二、回溯剪枝优化

回溯算法的效率通常较低，尤其在解空间非常大的时候。为此，剪枝技术是优化回溯算法的一个重要手段。剪枝的目的在于提前判断某一部分解是无效的，避免不必要的计算。

剪枝技巧：

1. 早期退出：当确定某个解不满足条件时，立即退出，不继续深入。
2. 减少不必要的递归：通过合理的判断条件避免冗余的递归调用。

---

📖 三、经典回溯问题与剪枝优化

1. N皇后问题

题目描述：
给定一个整数 n，表示 n x n 的棋盘，要求放置 n 个皇后，使得它们不能互相攻击。即：

• 同一行、同一列或同一对角线上的皇后不能放在一起。

要求：输出所有可能的放置方案。

剪枝方法：

1. 列冲突：使用一个数组记录每一列是否已经放置了皇后。
2. 左对角线冲突：使用一个数组记录每一条从左上到右下的对角线是否已经放置了皇后。
3. 右对角线冲突：使用一个数组记录每一条从右上到左下的对角线是否已经放置了皇后。

通过这三种冲突的检查，可以在递归时提前剪枝，避免不必要的递归调用。

代码实现（N皇后问题）：

import java.util.*;

public class NQueens {
    private List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        int[] positions = new int[n];  // 记录每一列的皇后位置
        solve(0, n, positions);
        return result;
    }

    private void solve(int row, int n, int[] positions) {
        if (row == n) {
            // 生成一个棋盘
            List<String> board = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] rowArr = new char[n];
                Arrays.fill(rowArr, '.');
                rowArr[positions[i]] = 'Q';
                board.add(new String(rowArr));
            }
            result.add(board);
            return;
        }

        // 剪枝：尝试每一列
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, positions)) {
                positions[row] = col; // 放置皇后
                solve(row + 1, n, positions); // 递归处理下一行
                // 如果不满足条件，继续尝试下一个位置
            }
        }
    }

    private boolean isValid(int row, int col, int[] positions) {
        for (int i = 0; i < row; i++) {
            // 检查列冲突，检查对角线冲突
            if (positions[i] == col || Math.abs(positions[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        NQueens nq = new NQueens();
        List<List<String>> solutions = nq.solveNQueens(4);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

代码解释：

• positions 数组表示每行皇后所在的列位置。positions[i] = j 表示第 i 行皇后放在第 j 列。
• isValid 方法：检查当前位置是否和已放置的皇后冲突（即列和对角线检查）。
• solve 方法：通过递归方式逐行尝试皇后的位置，符合条件的解保存至 result 列表中。

时间复杂度：

• 最坏情况是 O(n!)，因为每一行可能有 n 种选择。

---

2. 数独问题

题目描述：
给定一个数独的初始状态（部分格子已经填入数字），要求填充数独，保证数独的解是唯一的。

数独的规则：

• 每一行、每一列、每一个 3x3 的宫格内数字都不能重复。

剪枝方法：

• 利用数独的规则进行剪枝，即每次填入数字时，检查该数字是否满足行、列、宫的约束条件。
• 使用回溯法填入数字，当遇到不符合规则的情况时，立即回溯。

代码实现（数独问题）：

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (solve(board)) return true; // 递归尝试
                            board[i][j] = '.'; // 回溯
                        }
                    }
                    return false; // 无解
                }
            }
        }
        return true; // 解已填完
    }

    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        SudokuSolver solver = new SudokuSolver();
        char[][] board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '3', '1', '.', '.', '5'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solver.solveSudoku(board);
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(board[i]));
        }
    }
}

代码解释：

• solveSudoku 方法：调用递归回溯 solve 填充数独。
• isValid 方法：检查某个数字是否可以放置在 (row, col) 位置（检查行、列、宫的约束）。

时间复杂度：

• 最坏情况是填充所有 81 个格子，每个格子尝试 9 次，时间复杂度为 O(9^81)，但由于剪枝，实际运行时间通常较短。

---

📖 四、总结

1. 回溯算法的剪枝优化：

• N皇后 和 数独 都是典型的回溯问题，可以通过剪枝减少无效搜索，提升效率。
• N皇后剪枝：避免同一列、同一对角线上的皇后冲突。
• 数独剪枝：避免行、列、宫内数字重复。