leetcode 51 N queue
z
 2019-07-11 21:46:05  

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

image-20190711214520899

上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

输入: 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
27
28
29
30
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        ans = []
        board = [['.' for i in range(n)] for j in range(n)]
        
        def dfs(board, idx):
            for i in range(n):
                board[idx][i] = 'Q'
                if checked(board, idx, i):
                    if idx == n-1:
                        ans.append(["".join(t) for t in board])
                    else:
                        dfs(board, idx+1)
                board[idx][i] = '.'
        
        def checked(board, i, j):
            for k in range(i):
                if board[k][j] == 'Q':
                    return False
                for m in range(n):
                    if board[k][m] == 'Q' and i-k == abs(m-j):
                        return False
            return True
        dfs(board, 0)
        return ans