【每日算法Day 95】经典的N皇后问题

LeetCode 51. N 皇后 (opens new window)

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（即对于棋盘上的每一行、每一列、每一条对角线、反对角线，都只能有一个皇后）。

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

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

示例

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

解题思路

使用动态规划框架，在每一行选择一个点放下皇后再递归进入下一行。不过与一般的递归问题不同的是，我们不在递归树的最底层才检查皇后的摆放是否满足要求，而是在选择的时候就进行剪枝，仅对不造成冲突的选择进行递归。至于检查是否有冲突的部分，可以使用三个变量作为bitSet记录每列、每个对角线、每个反对角线上是否已经出现过皇后，并在递归进行选择和撤销选择时把对应位置分别置为1和0。

public class No51_NQuenes {
    private List<List<String>> resultSet = new ArrayList<>();
    private int n = 0;
    //使用三个变量作为bitSet记录每列、每个对角线、每个反对角线上是否已经出现过皇后
    private int columns = 0, diagonals = 0, reverseDiag = 0;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        backtrack(0, new ArrayList<>());
        return resultSet;
    }

    private void backtrack(int row, List<String> path) {
        //递归终止条件，添加到结果集
        if (row == n) {
            resultSet.add(new ArrayList<>(path));
            return;
        }

        //每行只选择一个点
        for (int i = 0; i < n; i++) {
            //剪枝，只对满足条件的点进行递归
            if (check(row, i)) {
                char[] str = new char[n];
                Arrays.fill(str, '.');
                str[i] = 'Q';
                path.add(new String(str));
                //递归到下一行中继续做选择
                backtrack(row + 1, path);
                //撤销选择
                path.remove(row);
                uncheck(row, i);
            }
        }
    }

    //检查选择的点是否会导致同列、同对角线、反对角线出现两个皇后
    private boolean check(int row, int col) {
        if (((columns >> col) & 1) == 1 || ((diagonals >> (row + col)) & 1) == 1 || ((reverseDiag >> (row - col)) & 1) == 1)
            return false;
        //如果没问题就把对应的位置为1，表示选择了该位置
        columns |= (1 << col);
        diagonals |= (1 << (row + col));
        reverseDiag |= (1 << (row - col));
        return true;
    }

    //撤销选择，将对应位置置为0
    private void uncheck(int row, int col) {
        columns &= ~(1 << col);
        diagonals &= ~(1 << (row + col));
        reverseDiag &= ~(1 << (row - col));
    }
}