leetcode 52 N queen II
z
 2019-07-11 21:09:12  

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

image-20190711211009204

上图为 8 皇后问题的一种解法。给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
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
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = [0]
        
        def dfs(position, ans, idx):
            for i in range(0, n):
                position[idx] = i
                if checked(position, idx):
                    if idx == n-1:
                        ans[0] += 1
                    else:
                        dfs(position, ans, idx+1)
        
        def checked(position, idx):
            for i in range(idx):
                if position[i] == position[idx] or idx-i == abs(position[idx] - position[i]):
                    return False
            return True
        
        dfs([0 for i in range(n)], ans, 0)
        return ans[0]