52. N皇后 II

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

N皇后 II

上图为 8 皇后问题的一种解法。

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

示例:

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

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

与N皇后的解题一致，省掉了创建字符串

class Solution {
    private int targetN; // n
    private int resultCnt;  // 解决方案的数量
    private boolean[] columnChoice;  // 已经被选择的列
    private boolean[] leftSlant;     // x-y=b,存储b
    private boolean[] rightSlant;    // x+y=b,存储b

    public int totalNQueens(int n) {
        targetN = n;
        resultCnt = 0;
        columnChoice = new boolean[targetN];
        leftSlant = new boolean[targetN * 2];
        rightSlant = new boolean[targetN * 2];
        searchQueen(0);
        return resultCnt;
    }

    private void searchQueen(int curRow) {
        if (curRow == targetN) {
            resultCnt ++;
            return;
        }
        for (int i = 0; i < targetN; i++) {
            // 满足当前列 && 对角线上
            if (!columnChoice[i] && !leftSlant[curRow - i + targetN] && !rightSlant[curRow + i]) {
                columnChoice[i] = true;
                leftSlant[curRow - i + targetN] = true;
                rightSlant[curRow + i] = true;
                searchQueen(curRow + 1);
                // 回退
                columnChoice[i] = false;
                leftSlant[curRow - i + targetN] = false;
                rightSlant[curRow + i] = false;
            }
        }
    }
}