尘雨尘风

数学与编程的爱好者

0%

leetcode题解51：N皇后

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

描述

该题来自于力扣第51题

分析

首先每个皇后只能在一行，同一行的不行，那么就可以用一个长度为n的数组记录当前的状态，比如[1, 3, 0, 2]表示，第0、1、2，3个皇后分别在1、3、0、2列；要放置n个皇后，大致用一下过程解决：
1. 由于每行必有且只有一个皇后，所以在第一行放置一个，可以放置到任意列；
2. 考虑下一行的皇后能够放到的位置，即可以放置的列有哪些？遍历所有可能，并继续考虑下一行

这样的过程，可以考虑为一棵树，然后深度优先遍历这棵树，得到的就是所有可能的方案；考虑遍历到其中某个结点node时，当前k个皇后的放置状态为数组arr，那么先找出第k+1个皇后的所有可能列candidates，然后遍历candidates，首先将第k+1个皇后的状态更新到arr，然后判断arr的长度是否达到了n，如果是，表明找到了一个解，记录下来；没有继续放置k+2，当node结点下面的所有可能都遍历完后，表示node结点已经完成了，应该要更新node结点的兄弟结点了，这是需要还原第k个皇后放置前的状态，即回溯下arr。

在已知前k个皇后状态数组arr的情况下，如何找到第k+1个皇后的所有可能列呢？仔细推导下发现，同一列的去掉，同一斜线的去掉，同一列的简单，就是arr中的值，同一斜线的就是列之差的绝对值和行之差的绝对值相等。

代码

python 
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
31
32
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        self.dfs([], n, ans)
        return ans

    def dfs(self, all_cols, n, ans):
        for c in self.find_candidates(all_cols, n):
            all_cols.append(c)
            if len(all_cols) == n:
                ans.append(self.format_ans(all_cols))

            self.dfs(all_cols, n, ans)
            all_cols.pop()

    def find_candidates(self, all_cols, n):
        all_valid = []
        for i in range(n):
            if self.isvalid(all_cols, i):
                all_valid.append(i)
        return all_valid

    def isvalid(self, all_cols, col):
        row = len(all_cols)
        for r, c in enumerate(all_cols):
            if c == col or abs(row - r) == abs(col - c):
                return False
        return True

    def format_ans(self, ans):
        s = ['.'*i + 'Q' + '.'*(len(ans)-i-1) for i in ans]
        return s
相关文章