[LeetCode] N-Queens II N皇后问题之二

The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.

[

 [".Q..",  // Solution 1

  "...Q",

  "Q...",

  "..Q."],

 ["..Q.",  // Solution 2

  "Q...",

  "...Q",

  ".Q.."]

]

这道题是之前那道 N-Queens 的延伸，说是延伸其实我觉得两者顺序应该颠倒一样，上一道题比这道题还要稍稍复杂一些，两者本质上没有啥区别，都是要用回溯法 Backtracking 来解，如果理解了之前那道题的思路，此题只要做很小的改动即可，不再需要求出具体的皇后的摆法，只需要每次生成一种解法时，计数器加一即可，代码如下：

解法一：

class Solution {

public:

    int totalNQueens(int n) {

        int res = ;

        vector<int> pos(n, -);

        helper(pos, , res);

        return res;

    }

    void helper(vector<int>& pos, int row, int& res) {

        int n = pos.size();

        if (row == n) ++res;

        for (int col = ; col < n; ++col) {

            if (isValid(pos, row, col)) {

                pos[row] = col;

                helper(pos, row + , res);

                pos[row] = -;

            }

        }

    }

    bool isValid(vector<int>& pos, int row, int col) {

        for (int i = ; i < row; ++i) {

            if (col == pos[i] || abs(row - i) == abs(col - pos[i])) {

                return false;

            }

        }

        return true;

    }

};

但是其实我们并不需要知道每一行皇后的具体位置，而只需要知道会不会产生冲突即可。对于每行要新加的位置，需要看跟之前的列，对角线，及逆对角线之间是否有冲突，所以我们需要三个布尔型数组，分别来记录之前的列 cols，对角线 diag，及逆对角线 anti_diag 上的位置，其中 cols 初始化大小为n，diag 和 anti_diag 均为 2n。列比较简单，是哪列就直接去 cols 中查找，而对角线的话，需要处理一下，如果我们仔细观察数组位置坐标的话，可以发现所有同一条主对角线的数，其纵坐标减去横坐标再加n，一定是相等的。同理，同一条逆对角线上的数字，其横纵坐标之和一定是相等的，根据这个，就可以快速判断主逆对角线上是否有冲突。任意一个有冲突的话，直接跳过当前位置，否则对于新位置，三个数组中对应位置都赋值为 true，然后对下一行调用递归，递归返回后记得还要还原状态，参见代码如下：

解法二：

class Solution {

public:

    int totalNQueens(int n) {

        int res = ;

        vector<bool> cols(n), diag( * n), anti_diag( * n);

        helper(n, , cols, diag, anti_diag, res);

        return res;

    }

    void helper(int n, int row, vector<bool>& cols, vector<bool>& diag, vector<bool>& anti_diag, int& res) {

        if (row == n) ++res;

        for (int col = ; col < n; ++col) {

            int idx1 = col - row + n, idx2 = col + row;

            if (cols[col] || diag[idx1] || anti_diag[idx2]) continue;

            cols[col] = diag[idx1] = anti_diag[idx2] = true;

            helper(n, row + , cols, diag, anti_diag, res);

            cols[col] = diag[idx1] = anti_diag[idx2] = false;

        }

    }

};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/52

类似题目：

N-Queens

参考资料：

https://leetcode.com/problems/n-queens-ii/

https://leetcode.com/problems/n-queens-ii/discuss/20058/Accepted-Java-Solution

https://leetcode.com/problems/n-queens-ii/discuss/20048/Easiest-Java-Solution-(1ms-98.22)

LeetCode All in One 题目讲解汇总(持续更新中...)

巴特西

[LeetCode] N-Queens II N皇后问题之二

最新文章

热门文章