用回溯 + DFS 搜索可能的解，用位运算优化空间复杂度

题目链接-来源：力扣（LeetCode）

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

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

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

示例 1：

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

思路：

简化版的解数独。由于我们需要给出 n 皇后问题的所有解，因此考虑使用回溯 + DFS 的方法搜索每一个可能的解。
暴力解的复杂度显然无法接受，我们每在棋盘放入一个皇后，就要维护一个冲突信息，记录与这个皇后相关的行、列、对角线，这样我们之后放置新的皇后时，就可以直接排除这些冲突的位置，即「剪枝」大大降低我们的解法复杂度。回溯时，我们需要用某种方式撤销掉与这个皇后相关的冲突信息，仿佛我们从未放置过它。
本题各种解法的效率主要取决于维护冲突信息以及剪枝的方法，最直观的，我们可以用一个 n* n 大小的二维 boolean 数组 conflicted[][] 存放棋盘上的冲突信息，每当我们放入一个皇后，就把其所在的行、列、对角线的尚未冲突的格子全部设置为 true （实际操作中，由于我们往往是一行一行地考虑皇后的放置，无形中已经规避了行冲突，所以无需记录行冲突信息，而只考虑列和两条对角线）。为了方便回溯，我们用一个列表 lock 存储这些新增冲突信息的坐标，待下层 dfs 返回后，我们再依次遍历 lock，将其中记载的对应位置 confilicted[][] 的冲突信息一一恢复为 false。
每次维护这个 conflicted[][] 的时间复杂度是 O(N)，如果我们采用一个 n 位二进制数表示冲突信息，用位运算的方法来维护，可以将时间复杂度降低到 O(1)，使得效率大大提升。
具体来讲，对于每一行而言，我们用三个二进制整数来分别传递列、主对角线、副对角线（以皇后位置为基准）冲突信息，记为 colConf、diagConf、antiConf。’0’ 表示可用，而 ‘1’ 表示此列会有冲突（用 0 表示可用，即「没有冲突」，是因为这样我们可以很方便地初始化为 0，如果用 1 表示可用的话，初始化会麻烦一点，但是可以方便我们后续的位运算，因为位运算中我们仍要用 1 表示可用）。
当前行的可用状态就是三个整数的或运算结果 colConf | diagConf | antiConf，为了方便后续位运算，我们需要改成用 ‘1’ 来表示可用，因此我们对这个结果取反。又因为我们只用到了低 n 位，需要用一个 n 位的全 1 掩码来过滤掉高位信息，记最终可用信息为 avail，则 avail = ((1 << n) - 1) & (~ (colConf | diagConf | antiConf))。
我们利用 avail 快速定位到可用的列下标，avail & (-avail) 可以找到其最低位的 ‘1’（即最靠前的可用位置），这个数字我们记为 toPut； avail & (avail - 1) 可以快速将这个 ‘1’ 置 ‘0’，方便我们下一轮继续操作。显然，当 avail 为 0，时，表示此行无可用位置，我们就可以跳出循环结束搜索。
定位到需要操作的列之后，我们同时拥有了行、列信息，就可以在这个位置放置一个皇后。我们维护冲突信息，并传递到下层递归，对于列冲突信息，toPut 就是我们新增的列冲突位置，于是我们应该向下传入 colConf | toPut；对于对角线信息，向下传递时除了要增加 toPut 信息外，我们还要进行对应的移位操作（下行的主对角线冲突信息相对本行而言右移了 1 列，由于我们的二进制数低位表示的是最左侧的列，所以应该进行左移操作，即 (diagConf | toPut) << 1 ，副对角线同理）。
当 DFS 的行数达到 n 行时，表明我们发现了一个可行解，只需将结果输出到结果集当中即可。
时间复杂度：O(n!)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<String>> solveNQueens(int n) {
        // Init
        this.n = n;
        queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> ret = new LinkedList<>();
        
        // Process
        dfs(ret, 0, 0, 0, 0);
        return ret;
    }
    private int[] queens;
    private int n;
    private void dfs(List<List<String>> ret, int row, int colConf, int diagConf, int antiConf) { // for the conflicted-indicator ints, 0 indicates available
        if (row == n) {// a solution is found
            ret.add(generateAns(queens));
            return;
        }
        
        int avail = ((1 << n) - 1) & (~ (colConf | diagConf | antiConf)); // 1 inidicates available
        while (avail != 0) {
            int toPut = avail & (-avail);
            avail = avail & (avail - 1);
            queens[row] = Integer.bitCount(toPut - 1);
            dfs(ret, row + 1, colConf | toPut, (diagConf | toPut) << 1, (antiConf | toPut) >> 1);
        }
    }
    
    private List<String> generateAns(int[] queens) {
        List<String> ans = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            ans.add(new String(row));
        }
        return ans;
    }
}