回溯算法：八皇后
将 $N$ 个皇后放在 $N \times N$ 的棋盘上，要求皇后不能处于同行、同列、同对角线上。没有什么取巧的方案，只能尝试所有情况后将可行的情况列出，因此可以使用回溯算法。
此题的难点在于判断皇后之间是否能相互攻击。如果将皇后所处的格子视为 $1$ ，其它格子视为 $0$ ，那么就可以使用位运算来判断。保证皇后不同行的方式很简单，只需要保证每一行只放置一个皇后即可。而如果想要保证皇后不同列，就需要记录之前行的皇后的位置。我们可以通过按位或和按位和进行记录和判断。
对于上面的例子，第一行我们可以记为 $0100$ 。到第二行通过按位和进行判断：$0100 \And 0001$ ，如果不为 $0$ ，说明发生冲突。如果没有冲突，那么可以通过按位或获取新值：$0100 | 0001 = 0101$ 。重复上述步骤即可保证皇后处于不同列。
如果要保证皇后不处于同对角线，进行观察可以发现：下一行的皇后不能处于上一行皇后的左一格或者右一格，不能处于上上一行皇后的左二格或者右二格……也就是每过一行，就让之前行的皇后统一左移或者右移一格，然后再使用类似于之前判断皇后是否同列的方法进行判断就行了。我们可以使用两个数字 $left$ 和 $right$，专门用于记录之前行皇后的左移或者右移。再以上面的例子，第二行的 $left$ 为 $1000$ ，第三行为 $0010$ ；第二行的 $right$ 为 $0010$ ，第三行的 $right$ 为 $0001$ 。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<String> queens = new ArrayList<>();
List<List<String>> res = new ArrayList<>();
backtrack(res, queens, n, 0, 0, 0);
return res;
}
private void backtrack(
List<List<String>> res, List<String> queens, int n, int visit, int left, int right) {
if (queens.size() == n) {
res.add(new ArrayList<>(queens));
return;
}
for (int i = 0; i < n; i++) {
int position = 1 << (n - i - 1);
if ((visit & position) != 0 || (left & position) != 0 || (right & position) != 0) continue;
char[] chars = new char[n];
Arrays.fill(chars, '.');
chars[i] = 'Q';
queens.add(String.valueOf(chars));
backtrack(res, queens, n, visit | position, (left | position) << 1, (right | position) >> 1);
queens.remove(queens.size() - 1);
}
}
}
$visit$ 、$left$ 、$right$ 分别用于判断同列、左对角线和右对角线的冲突。每次递归时，通过按位或以及左移和右移运算符移动之前行皇后的位置。