卖萌的弱渣

I am stupid, I am hungry.

N-Queens II

Follow up for N-Queens problem.

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

Solution

方法和N-Queen相同

(N-Queens2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """

        visited = [-1]*n
        self.ret = 0
        self.sol(visited, n, 0)
        return self.ret

    def sol(self, visited, n, index):

        def check(visited,row,col):
            for i in range(row):
                if visited[i] == col or abs(i-row) == abs(visited[i] - col):
                    return False
            return True

        if index == n:
            self.ret += 1
            return

        for j in range(n):
            if check(visited,index,j):
                visited[index] = j
                self.sol(visited,n,index+1)