【回溯】Leetcode 51. N 皇后【困难】

N 皇后

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

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

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

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

示例1：
在这里插入图片描述
输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

解题思路

1、使用回溯算法来生成所有不同的N皇后问题的解决方案。
2、在每一行中，依次尝试放置皇后，并检查是否符合规则，即不在同一行、同一列、同一对角线上。
3、使用递归回溯的方法，尝试放置皇后，并继续向下一行递归放置。
4、如果当前行放置皇后后，无法找到合适的位置，则回溯到上一行重新尝试。

解题步骤

1、初始化棋盘：创建一个大小为 n×n 的棋盘，用二维数组表示，初始时所有位置都为空（用 ‘.’ 表示）。
2、回溯搜索：从第一行开始逐行放置皇后，在放置每一行的皇后时，都需要检查当前位置是否合法。
如果合法，则将皇后放置在该位置，并继续递归地放置下一行的皇后；
如果不合法，则尝试下一个位置。在递归的过程中，需要记录已经放置的皇后的位置，以便进行回溯。
3、递归结束条件：当放置了所有的皇后时，即递归到达了棋盘的最后一行，
此时找到了一个可行解，将该解保存下来。然后回溯到上一行，尝试放置下一个皇后，继续搜索其他解。
4、合法性检查：在放置皇后时，需要检查当前位置是否与已放置的皇后冲突。
具体地，需要检查当前位置的同一列、同一行、左上对角线和右上对角线是否已经存在皇后。如果存在冲突，则当前位置不合法，需要尝试下一个位置。
5、保存解：当找到一个合法的解时，将该解保存到结果集中，
并继续搜索其他可能的解。
6、回溯：在搜索过程中，如果发现当前位置无法放置皇后，或者已经找到了一个解，
则需要回溯到上一步，撤销当前操作，尝试其他可能的选择。
7、返回结果：当搜索结束时，返回所有找到的合法解。

java实现

public class NQueens {

    public List<List<String>> solveNQueens(int n) {
        //保存结果集
        List<List<String>> result = new ArrayList<>();
        //初始化棋盘
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        //放置皇后
        backtrack(result, board, 0);
        return result;
    }

    //回溯
    private void backtrack(List<List<String>> result, char[][] board, int row) {
        if (row == board.length) {
            result.add(constructSolution(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            ///判断放置位置是否符合规则
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(result, board, row + 1);
                //撤销此次产生的影响,回溯到上一步
                board[row][col] = '.';
            }
        }
    }

    //判断放置位置是否符合规则
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            // 检查列是否有皇后冲突
            if (board[i][col] == 'Q') return false;
            //获取行的差值，用于下面左上方、右上方对角线对应的位置
            //对于[row][col]因i= row-d 转换成[i+d,col]，所以[i,col-d]一定在其左上方
            // 随着i从0到row变化，d的值也在改变，d=1，board[i][col - d]就是[row][col]左上方的格子，
            // d=2，board[i][col - d]就是[row][col]左上方的左上方的格子
            int d = row - i;
            // 检查左上方对角线是否有皇后冲突
            if (col - d >= 0 && board[i][col - d] == 'Q') return false;
            // 检查右上方对角线是否有皇后冲突
            if (col + d < board.length && board[i][col + d] == 'Q') return false;
        }
        return true;
    }

    //记录解决方案
    private List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) {
            solution.add(String.valueOf(row));
        }
        return solution;
    }

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