首页 > 代码库 > 【LeetCode】N-Queens II

【LeetCode】N-Queens II

     题意:

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

     思路:

     n 皇后问题,算可能的方案数。基本的简单想法是对每一行处理,处理的时候尝试在每一列放一个皇后,只要不冲突就向下递归,不断计算合法方案数。


     代码:

     C++

class Solution {
public:
    int totalNQueens(int n) {
        /*初始化 vector 变量,第 i 个数代表第 i 行的皇后在哪一列*/
        vector<int> chess(n,-1);
        int ans = 0;
        /*解决问题*/
        solveQueen(0,n,chess.begin(),ans);
        return ans;
    }

    void solveQueen(int r,int n,vector<int>::iterator chess,int &ans)
    {
        /*r 等于 n 时每一行都有了皇后*/
        if(r == n)
        {
            ans++;
            return;
        }

        /*对当前行看哪一列可以放皇后*/
        for(int i = 0;i < n;++i)
        {
            *(chess+r) = i;
            /*检查合法性*/
            if(check(chess,r,n))
            {
                /*向下递归*/
                solveQueen(r+1,n,chess,ans);
            }
        }
    }

    /*检查冲突*/
    bool check(vector<int>::iterator chess,int r,int n)
    {
        /*对之前的每一行*/
        for(int i = 0;i < r;++i)
        {
            /*计算两列的距离*/
            int dis = abs(*(chess+r) - *(chess+i));
            /* dis = 0 则在同一列, dis = r- 1 则构成等腰三角形,即对角线*/
            if(dis == 0 || dis == r - i)
                return false;
        }
        return true;
    }
};
     Python:

class Solution:
    # @return an integer
    def totalNQueens(self, n):
        self.array = [0 for i in range(0,n)]
        self.ans = 0
        self.sloveQueen(0,n)
        return self.ans

    def sloveQueen(self,r,n):
        if r == n:
            self.ans += 1
            return
        for i in range(0,n):
            self.array[r] = i
            if self.check(r,n):
                self.sloveQueen(r+1,n)

    def check(self,r,n):
        for i in range(0,r):
            dis = abs(self.array[r] - self.array[i])
            if dis == 0 or dis == r - i:
                return False
        return True

【LeetCode】N-Queens II