LeetCode N-Queens
LeetCode queens
2023-09-11 14:14:42 时间
LeetCode解题之N-Queens
原题
经典的八皇后问题的普通情况。用Python如何来高速地解决呢?
注意点:
- 皇后用”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))
欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
相关文章
- Leetcode: Assign Cookies
- Leetcode: Verify Preorder Sequence in Binary Search Tree
- Leetcode: Isomorphic Strings
- Leetcode: N-Queens II
- Leetcode: N-Queens
- LeetCode Decode Ways
- [LeetCode][Java] N-Queens II
- LeetCode高频题956:数组arr,能否把数组取出若干个数,使得取出数之和,与剩下数的和相同
- 【LeetCode】168. Excel Sheet Column Title
- 【LeetCode】51. N-Queens
- 【LeetCode】Word Break 解题报告
- Leetcode 236 Lowest Common Ancestor of a Binary Tree
- 【Leetcode】Linked List Cycle II
- 【leetcode】148:排序链表
- 【leetcode】108:将有序数组转化为二叉搜索树
- [LeetCode] 945. Minimum Increment to Make Array Unique 使数组没有重复数字的最小增量
- [LeetCode] Prime Number of Set Bits in Binary Representation 二进制表示中的非零位个数为质数
- [LeetCode] 52. N-Queens II N皇后问题之二
- [LeetCode] 51. N-Queens N皇后问题
- leetcode 236. Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先(中等)
- leetcode 51. N-Queens N 皇后(困难)
- leetcode算法257.二叉树的所有路径