51. N皇后 I

雨点打透心脏的1/2处 2022-04-23 08:26 173阅读 0赞

### 题目描述 ###

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
    
    每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
    
    示例:
    
    输入: 4
    输出: [
     [".Q..",  // 解法 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // 解法 2
      "Q...",
      "...Q",
      ".Q.."]
    ]
    解释: 4 皇后问题存在两个不同的解法。

![在这里插入图片描述][20190129164435845.png]

### 分析 ###

N皇后 攻击就是 每个皇后的横竖撇捺 4个方向 都没有其他皇后，DFS扫棋盘，按行扫，看其他3个方向是否有其他皇后，都用set()存储，列用col ，撇这一行上 i+j 相等，捺这一行上i-j 相等 。另外注意题目要求的返回格式

### 解法 ###

class Solution:
        def solveNQueens(self, n):
            if n <1 :return []
            self.result = []
            self.cols = set()
            self.pie = set()
            self.na = set()
            self.DFS(n,0,[])
            return self._generate_result(n)
    
        def DFS(self, n, row, cur_state):
            # recursion terminator
            if row >= n:
                self.result.append(cur_state)
                return
            for col in range(n):
                if col in self.cols or row + col in self.pie or row - col in self.na:
                    # die!
                    continue
    
                # update flags
                self.cols.add(col)
                self.pie.add(row + col)
                self.na.add(row - col)
    
                self.DFS(n, row + 1, cur_state + [col])
    
                self.cols.remove(col)
                self.pie.remove(row + col)
                self.na.remove(row - col)
    
        def _generate_result(self, n):
            board = []
            for res in self.result:
                for i in  res:
                    board.append("." * i + "Q" + "." * (n - i -1))
            return [board[i: i + n] for  i in range(0, len(board), n)]

[20190129164435845.png]: /images/20220322/c9e8d6df11664172a60a76dbc545dac0.png