回溯算法:八皇后

原题地址:Problem 51

        将 $N$ 个皇后放在 $N \times N$ 的棋盘上,要求皇后不能处于同行、同列、同对角线上。没有什么取巧的方案,只能尝试所有情况后将可行的情况列出,因此可以使用回溯算法。
        此题的难点在于判断皇后之间是否能相互攻击。如果将皇后所处的格子视为 $1$ ,其它格子视为 $0$ ,那么就可以使用位运算来判断。保证皇后不同行的方式很简单,只需要保证每一行只放置一个皇后即可。而如果想要保证皇后不同列,就需要记录之前行的皇后的位置。我们可以通过按位或和按位和进行记录和判断。

$$ .\ \ Q\ .\ \ .\ \ \\ .\ \ .\ \ .\ \ Q\ \\ Q\ .\ \ .\ \ .\ \ \\ .\ \ .\ \ Q\ .\ \ \\ $$

        对于上面的例子,第一行我们可以记为 $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$ 分别用于判断同列、左对角线和右对角线的冲突。每次递归时,通过按位或以及左移和右移运算符移动之前行皇后的位置。