【算法问题】N 皇后问题

参考：52.N 皇后 II

1.问题定义

（1）在国际象棋的规则中，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N 皇后问题指的是如何将 N 个皇后放置在 N × N 的棋盘上，并且使皇后彼此之间不能相互攻击。即给你一个整数 N ，返回所有不同的 N 皇后问题的解决方案数量（1 ≤ N ≤ 16）。

（2）例如，当 N = 4 时，有 2 种解决方案，具体如下图所示：

2.思路分析

2.1.基于数组的回溯

（1）一种比较直观的做法是暴力枚举将 N 个皇后放置在 N×N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。显然，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式得到可能的解的数量。

（2）回溯的具体做法是：使用一个数组（下面代码中的数组 queens，长度为 N）记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，我们将记录解决方案总数的变量 count 加一即可。

（3）在判断新放置的皇后是否与之前任何一个已经放置的皇后在同一列以及同一条斜线上时，我们可以采用二维坐标系中斜率的概念来快速判断，以下图为例，A、B、C、D 这三个皇后的坐标分别为 (3, 1)、(2, 0)、(0, 1)、(1, 3)，其中 D 是新放置的皇后。

• 如果新放置的皇后与之前任何一个已经放置的皇后的纵坐标相等，那么它们必然在在同一列，例如下图中的皇后 A 与皇后 C 在同一列；
• 如果新放置的皇后与之前任何一个已经放置的皇后的坐标所在的直线的斜率为 1 或者 -1，那么它们必然在同一条斜线上，例如下图中直线 AB 的斜率为 -1，直线 AD 的斜率为 1；

（4）而且，这样一来之前定义的数组 queens 正好可以用来表示每个皇后在棋盘上的坐标，即 queens[i] = j 表示的对应皇后的坐标为 (i, j)，那么对于任意两个皇后 Q1(i, j) 和 Q2(x, y)：

• 如果 j == y，那么说明 Q1 和 Q2 在同一列；
• 如果 (j - y) / (i - x) == ±1，即 |j - y| == |i - x|，那么说明 Q1 和 Q2 在同一斜线上；

2.2.基于集合的回溯

（1）思路 2.1 是使用一个数组记录每行放置的皇后的列下标，并且根据斜率的相关知识来判断新放置的皇后是否与之前任何一个已经放置的皇后在同一列以及同一条斜线上。但是在实际判断过程中，我们还是需要将新放置的皇后与之前放置的皇后逐一比较。

（2）那么为了加快判断的过程，我们可以使用“空间替换时间”的策略。具体来说，为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、diagonals1 和 diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后。

• 列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N?1，使用列的下标即可明确表示每一列。
• 我们假设方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
  
• 我们假设方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
  

上面的两张图来自 52.N 皇后 II

（3）每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

2.3.基于位运算的回溯

有关位运算的相关技巧可与参考【算法技巧】位运算这篇文章。

（1）思路 2.2 使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 N 个元素，因此集合的空间复杂度是 O(N)。如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 O(N) 降到 O(1)。

（2）具体做法是，使用三个整数 columns、diagonals1 和 diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后，每个整数有 N 个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。

（3）得到这三个整数的计算方法如下：

• 初始时，三个整数的值都等于 0，表示没有放置任何皇后；
• 在当前行放置皇后，如果皇后放置在第 i 列，则将三个整数的第 i 个二进制位（指从低到高的第 i 个二进制位）的值设为 1；
• 进入下一行时，columns 的值保持不变，diagonals1 左移一位，diagonals2 右移一位，由于棋盘的最左列对应每个整数的最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反（对棋盘的移位操作方向是 diagonals1 右移一位，diagonals2 左移一位）。

3.代码实现 (Java)

3.1.基于数组的回溯

class Solution {
    //记录解决方案总数
    int count = 0;

    public int totalNQueens(int n) {
        // queens[t] 表示第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列 (0 ≤ t < n)
        int[] queens = new int[n];
        backtrack(queens, 0);
        return count;
    }

    public void backtrack(int[] queens, int t) {
        int n = queens.length;
        if (t == n) {
        	//找到一种解决方案
            count++;
            return;
        }
        //遍历当前第 t 个皇后在第 t 行的第 0 ~ n - 1 列
        for (int i = 0; i < n; i++) {
            //将第 t 个皇后放在棋盘的第 t 行的第 i 列
            queens[t] = i;
            //判断第 t 个皇后能不能放在当前位置
            if (check(queens, t)) {
                //能够放在当前位置，开始判断下一个皇后
                backtrack(queens, t + 1);
            }
        }
    }

    //在一行只放一个皇后的前提下，判断第 t 个皇后能否放在当前位置
    public boolean check(int[] queens, int t) {
        //判断当前第 t 个皇后是否与前 0 ~ t - 1 行的皇后能相互攻击
        for (int i = 0; i < t; i++) {
            /*
                t - i == Math.abs(queens[i] - queens[t]): 当前第 t 个皇后与之前的第 i 个皇后在同一斜线上
                queens[i] == queens[t]: 当前第 t 个皇后与之前的第 i 个皇后在同一纵行上
            */
            if ((t - i) == Math.abs(queens[i] - queens[t]) || queens[i] == queens[t]) {
                return false;
            }
        }
        return true;
    }
}

3.2.基于数组的回溯

class Solution {

    //记录解决方案总数
    int count = 0;

    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(n, 0, columns, diagonals1, diagonals2);
        return count;
    }

     /*
        n: 棋盘的大小，也就是皇后的数量
        row: 当前皇后正在放置的行数，初始值为 0
        columns: 存储之前放置的皇后所在的列
        diagonals1: 方向一的斜线，存储该斜线上皇后坐标的行下标与列下标之差
        diagonals2: 方向二的斜线，存储该斜线上皇后坐标的行下标与列下标之和
     */
    public void backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            count++;
            return;
        }
        //遍历当前第 row 个皇后在第 t 行的第 0 ~ n - 1 列
        for (int i = 0; i < n; i++) {
            if (columns.contains(i)) {
                //当前皇后所在的列已有其它皇后占据
                continue;
            }
            int diagonal1 = row - i;
            if (diagonals1.contains(diagonal1)) {
                //当前皇后所在的斜线(从左上往右下方向)有其它皇后占据
                continue;
            }
            int diagonal2 = row + i;
            if (diagonals2.contains(diagonal2)) {
                //当前皇后所在的斜线(从左下往右上方向)有其它皇后占据
                continue;
            }
            columns.add(i);
            diagonals1.add(diagonal1);
            diagonals2.add(diagonal2);
            //能够放在当前位置，开始判断下一个皇后
            backtrack(n, row + 1, columns, diagonals1, diagonals2);
            columns.remove(i);
            diagonals1.remove(diagonal1);
            diagonals2.remove(diagonal2);
        }
    }
}

3.3.基于位运算的回溯

class Solution {

    //记录解决方案总数
    int count = 0;

    public int totalNQueens(int n) {
        //调用回溯函数，从第 0 行开始放置皇后
        backtrack(n, 0, 0, 0, 0);
        return count;
    }

    public void backtrack(int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            //找到了一个解决方案
            count++;
            return;
        }
        /*
        	计算可用的位置，假设 n = 8，columns、diagonals1 、diagonals2 的二进制表示分别如下:
        	0001 0100
        	0011 0000
        	0000 1001
			columns | diagonals1 | diagonals2: 其二进制表示中，所有值为 1 的位置均不可放置皇后，例如 0000 ... 0011 1101
			~(columns | diagonals1 | diagonals2): 其二进制表示中，所有值为 0 的位置均不可放置皇后，例如 1111 ... 1100 0010
			((1 << n) - 1) & (~(columns | diagonals1 | diagonals2)): 保证从低 0 ~ n - 1 位范围内所有值为 1 的位置才能放置皇后
		*/
        int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
        //不断尝试可用的位置
        while (availablePositions != 0) {
            //取出最右边的可用位置放置皇后
            int position = availablePositions & (-availablePositions);
            //将该位置从可用位置中移除
            availablePositions = availablePositions & (availablePositions - 1);
            backtrack(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
        }
    }
}

4.扩展

如果需要求出具体每种解决方案，那么只需在找到每种解决方案时，记录一下即可，具体代码如下：

class Solution {

    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        // queens[t] 表示第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列 (0 ≤ t < n)
        int[] queens = new int[n];
        backtrack(queens, 0);
        return res;
    }

    public void backtrack(int[] queens, int t) {
        int n = queens.length;
        if (t == n) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (j == queens[i]) {
                        builder.append('Q');
                    } else {
                        builder.append('.');
                    }
                }
                tmp.add(builder.toString());
            }
            res.add(tmp);
            return;
        }
        for (int i = 0; i < n; i++) {
            queens[t] = i;
            if (check(queens, t)) {
                backtrack(queens, t + 1);
            }
        }
    }

    public boolean check(int[] queens, int t) {
        for (int i = 0; i < t; i++) {
            if ((t - i) == Math.abs(queens[i] - queens[t]) || queens[i] == queens[t]) {
                return false;
            }
        }
        return true;
    }
}