经典回溯算法应用案例（1） - 八皇后问题

1. 问题背景与描述

八皇后问题是经典的回溯算法应用问题之一。它的目标是要在一个 8x8 的国际象棋棋盘上放置 8 个皇后，使得它们互不攻击。由于皇后可以横向、纵向和斜向攻击，所以在放置时必须确保每个皇后都不与其他皇后处于同一行、同一列或同一对角线。

八皇后问题不仅是一个有趣的数学问题，而且它也为我们展示了回溯算法的强大能力，尤其是在解决组合和排列问题时，回溯算法能高效地探索解空间。

2. 回溯算法在八皇后问题中的应用

回溯算法在八皇后问题中的应用非常直接：我们从棋盘的第一行开始，依次尝试在每一行上放置一个皇后，然后递归地检查下一行的放置情况。如果某一步放置皇后时发生了冲突（即皇后会互相攻击），则回退到上一步，尝试其他可能的放置方式，直到所有皇后都成功放置。

关键步骤：

逐行放置皇后：从第一行开始，依次在每一行尝试放置皇后。
判断冲突：每次放置皇后时，必须检查当前皇后是否与已经放置的皇后发生冲突。冲突的条件是：它们不可以处于同一列或同一斜线上。
回溯：如果当前行的某个位置放置了皇后并导致冲突，那么就回退到上一行，尝试其他位置。

通过这种方式，我们能够系统地遍历所有可能的放置情况，找到所有不冲突的解。

3. 实现步骤与代码解析

我们来实现八皇后问题的回溯算法。思路是使用一个数组 board[] 来表示棋盘，其中 board[i] 表示第 i 行皇后所在的列位置。例如，如果 board[i] = j，那么就表示第 i 行的皇后放在了第 j 列。

代码实现

public class EightQueens {
    // 存储解
    private static final int N = 8;  // 棋盘的大小
    private int[] board = new int[N];  // 存储皇后的位置

    public static void main(String[] args) {
        EightQueens eq = new EightQueens();
        eq.solve();
    }

    // 解八皇后问题
    public void solve() {
        solveNQueens(0);  // 从第0行开始
    }

    // 递归回溯算法
    private void solveNQueens(int row) {
        if (row == N) {  // 当放置完所有皇后时，输出结果
            printSolution();
            return;
        }
        
        for (int col = 0; col < N; col++) {
            if (isSafe(row, col)) {  // 判断当前位置是否安全
                board[row] = col;  // 放置皇后
                solveNQueens(row + 1);  // 递归到下一行
                // 如果没有找到解，回溯
                board[row] = -1;
            }
        }
    }

    // 判断当前位置是否安全
    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {  // 检查前面的所有行
            if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false;  // 同列或者同对角线，返回 false
            }
        }
        return true;
    }

    // 打印当前解
    private void printSolution() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i] == j) {
                    System.out.print("Q ");  // 放置皇后
                } else {
                    System.out.print("* ");  // 空格
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

代码解析

数组表示棋盘：board 数组用来存储每一行皇后的位置。例如，board[i] = j 表示第 i 行的皇后放置在第 j 列。
回溯函数 solveNQueens：从第 0 行开始，递归地尝试放置皇后。对于每一行，我们遍历所有列，尝试在不冲突的位置放置皇后。如果当前位置安全（即不与前面行上的皇后冲突），我们将皇后放在当前位置，并递归处理下一行。
冲突检测函数 isSafe：此函数检查当前列和当前斜线上是否有皇后。如果有冲突，返回 false，否则返回 true。
打印解 printSolution：每次找到一个合法解后，打印出棋盘的布局。