LeetCode N-Queens

页面导航:首页 > 软件编程 > C 语言 > LeetCode N-Queens

LeetCode N-Queens

来源: 作者: 时间:2016-01-15 14:31 【

LeetCode解题之N-Queens原题经典的八皇后问题的一般情况,用Python怎样来快速地解决呢?注意点:皇后用Q表示,空白用 表示例子:输入: n = 4输出: [ [ Q ,

经典的八皇后问题的一般情况,用Python怎样来快速地解决呢?

8-queens

注意点:

皇后用”Q”表示,空白用”.”表示

例子:

输入: n = 4

输出:

[  ['.Q..', 
    '...Q', 
    'Q...', 
    '..Q.'], 

   ['..Q.', 
    'Q...', 
    '...Q', 
    '.Q..']]

解题思路

用三个数组来表示列、正反对角线的占用情况。一行行的遍历,如果没有冲突就把相应的位置置为占用,继续处理下一行,并记录改行的皇后放在了哪一列,当皇后都放完后,根据记录的列号来拼出结果。进行回溯时要把占用的位置还回去。对角线位置的计算要小心(尤其是反对角线),可以把顶点带进去计算验证一下。

AC源码

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.col = [False] * n
        self.diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        self.result = []
        self.recursive(0, n, [])
        return self.result

    def recursive(self, row, n, column):
        if row == n:
            self.result.append(list(map(lambda x: '.' * x + 'Q' + '.' * (n - 1 - x), column)))
        else:
            for i in range(n):
                if not self.col[i] and not self.diag[row + i] and not self.anti_diag[n - i + row]:
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = True
                    self.recursive(row + 1, n, column + [i])
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = False


if __name__ == "__main__":
    print(Solution().solveNQueens(5))
 
Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<