N皇后 | LeetCode-51 | 回溯算法

回溯算法练习题

---

LeetCode链接：51. N 皇后

---

1.题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

2.题解

2.1 回溯算法-写法1

class Solution {
    // 定义保存最终结果的列表，每个解法是一个List<String>，代表棋盘上的布局
    List<List<String>> result = new ArrayList<>();
    // 定义保存当前棋盘路径的列表，存放字符串形式的每一行布局
    List<String> path = new ArrayList<>();

    // 主函数，负责初始化棋盘并调用回溯算法
    public List<List<String>> solveNQueens(int n) {
        // 定义棋盘，char数组，用 '.' 表示空位
        char[][] chessboard = new char[n][n];
        // 初始化棋盘，每个位置都填充为 '.'
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chessboard[i][j] = '.';
            }
        }
        backtracking(chessboard, n, 0);// 开始回溯算法，从第0行开始放置皇后
        return result;// 返回所有可能的解法
    }

    // 回溯函数，递归尝试每一行的不同列位置放置皇后
    public void backtracking(char[][] chessboard, int n, int depth) {
        // 如果当前路径长度等于n，说明已经找到一个解法，加入结果集中
        if (path.size() == n) {
            result.add(new ArrayList<>(path));  // 将当前路径加入到结果中
            return;  // 回溯终止条件
        }

        // 尝试在当前行（depth）每一列放置皇后
        for (int col = 0; col < n; col++) {
            // 如果当前位置放置皇后合法
            if (isValid(chessboard, n, depth, col)) {
                // 构建当前行的字符串表示，并在指定列放置 'Q'
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) sb.append(".");  // 初始化为全是空位 '.'
                sb.replace(col, col + 1, "Q");  // 在col列位置放置皇后 'Q'
                path.add(sb.toString());// 将当前行加入路径
                chessboard[depth][col] = 'Q';// 在棋盘上放置皇后
                backtracking(chessboard, n, depth + 1);// 递归放置下一行的皇后
                chessboard[depth][col] = '.';// 回溯，移除当前行的皇后
                
                // 回溯，移除当前行的字符串布局
                path.remove(path.size() - 1);  // 使用 path.removeLast() 会出错，因为 List 不支持这个方法
            }
        }
    }

    // 判断在棋盘的(row, col)位置放置皇后是否合法
    public boolean isValid(char[][] chessboard, int n, int row, int col) {
        // 判断当前列是否有其他皇后
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') return false;  // 当前列已经有皇后，放置非法
        }

        // 判断135度对角线（左上到右下）是否有其他皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') return false;  // 135度对角线上已经有皇后
        }

        // 判断45度对角线（右上到左下）是否有其他皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') return false;  // 45度对角线上已经有皇后
        }
        
        // 没有冲突，放置合法
        return true;
    }
}

2.2 回溯算法-写法1-优化

class Solution {
    // 存储最终结果的列表，每个解法是一个 List<String>，表示棋盘的布局
    List<List<String>> result = new ArrayList<>();
    
    // 主函数，初始化棋盘并调用回溯算法
    public List<List<String>> solveNQueens(int n) {
        // 定义棋盘，初始化为 '.' 表示空位
        char[][] chessboard = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                chessboard[i][j] = '.';
            }
        }
        
        // 调用回溯函数，开始从第0行放置皇后
        backtracking(chessboard, n, 0);
        
        // 返回所有可能的解法
        return result;
    }

    // 回溯函数，递归尝试每一行的不同列放置皇后
    public void backtracking(char[][] chessboard, int n, int depth) {
        // 如果已经放置了n个皇后，说明找到一个解，保存结果
        if(depth == n) {
            result.add(arrayToList(chessboard));  // 将棋盘的当前布局转为列表并加入结果
            return;  // 回溯终止条件
        }

        // 尝试在当前行（depth）的每一列放置皇后
        for(int col = 0; col < n; col++) {
            // 如果在 (depth, col) 放置皇后合法
            if(isValid(chessboard, n, depth, col)) {
                // 在棋盘上放置皇后
                chessboard[depth][col] = 'Q';
                
                // 递归放置下一行的皇后
                backtracking(chessboard, n, depth + 1);
                
                // 回溯，撤销当前行的皇后
                chessboard[depth][col] = '.';
            }
        }
    }

    // 将棋盘转换为字符串列表，便于保存结果
    public List<String> arrayToList(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for(char[] chs : chessboard) {
            // 将每一行的字符数组转换为字符串并加入列表
            list.add(String.copyValueOf(chs));
        }
        return list;
    }

    // 判断在棋盘 (row, col) 位置放置皇后是否合法
    public boolean isValid(char[][] chessboard, int n, int row, int col) {
        // 判断当前列是否有其他皇后
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') return false;  // 同列有冲突
        }

        // 判断135度对角线（左上到右下）是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') return false;  // 135度对角线上有冲突
        }

        // 判断45度对角线（右上到左下）是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') return false;  // 45度对角线上有冲突
        }
        
        // 没有冲突，放置合法
        return true;
    }
}