LeetCode——N皇后 II

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

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

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

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

提示：皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或七步，可进可退。（引用自 百度百科 - 皇后 ）

A：
同I中的回溯法

    private int result;

    public int totalNQueens(int n) {
        if (n <= 1)
            return n;
        ArrayList<Integer> l = new ArrayList<>();
        result = 0;
        help(0, n, l);
        return result;
    }

    private void help(int row, int n, ArrayList<Integer> l) {
        if (row == n) {
            result++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!l.contains(col)) {
                if (!isDiagonal(l, col)) {
                    l.add(col);
                    help(row + 1, n, l);
                    l.remove(l.size() - 1);
                }
            }
        }
    }

    private boolean isDiagonal(ArrayList<Integer> l, int col) {
        int currRow = l.size();
        for (int row = 0; row < l.size(); row++) {
            if (Math.abs(currRow - row) == Math.abs(col - l.get(row))) {
                return true;
            }
        }
        return false;
    }

LeetCode——N皇后 II

原文：https://www.cnblogs.com/xym4869/p/13139421.html