[52]N皇后 II.java

//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回 n 皇后不同的解决方案的数量。 
//
// 示例: 
//
// 输入: 4
//输出: 2
//解释: 4 皇后问题存在如下两个不同的解法。
//[
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
// 
//
// 
//
// 提示： 
//
// 
// 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N
//-1 步，可进可退。（引用自 百度百科 - 皇后 ） 
// 
// Related Topics 回溯算法 
// 👍 146 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private int result = 0;

    public int totalNQueens(int n) {
        int[][] checkBoard = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(checkBoard[i], 0);
        }
        result = 0;
        calcute(checkBoard, 0, n);
        return result;
    }

    private void calcute(int[][] checkBoard, int height, int n) {
        for (int i = 0; i < n; i++) {
            if (judge(checkBoard, i, height, n)) {
                checkBoard[height][i] = 1;
                if (height == n - 1) {
                    result++;
                } else {
                    calcute(checkBoard, height + 1, n);
                }
                checkBoard[height][i] = 0;
            }
        }
    }

    private boolean judge(int[][] checkBoard, int width, int height, int n) {
        int sum = 0;
        for (int i = 1; i <= height; i++) {
            sum += checkBoard[height - i][width];
            if (width - i >= 0) {
                sum += checkBoard[height - i][width - i];
            }
            if (width + i < n) {
                sum += checkBoard[height - i][width + i];
            }
        }
        return sum == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)