LeetCode-52.N皇后 II(N-Queens II)

原创
2021/02/20 08:00
阅读数 106

这道题,其实和上一题差不多,上一题答案都知道了,个数也就是顺带的事情

52. N皇后 II

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

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

示例:

输入: 4输出: 2解释: 4 皇后问题存在如下两个不同的解法。[ [".Q..",  // 解法 1  "...Q",  "Q...",  "..Q."],
["..Q.", // 解法 2 "Q...", "...Q", ".Q.."]]

提示:

皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一或 N-1 步,可进可退。(引用自 百度百科 - 皇后 )

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/n-queens-ii/

Link:https://leetcode.com/problems/n-queens-ii/

DFS

O(N!)

回溯

class Solution:    def totalNQueens(self, n: int) -> int:        self.res = 0        self.helper(n, [], [], [])        return self.res
def helper(self, n: int, pos: List[int], diffs:List[int], sums:List[int]) -> None:
if len(pos) == n: self.res += 1 return
row = len(pos) for col in range(n): if col in pos or row - col in diffs or row + col in sums: continue
self.helper(n, pos + [col], diffs + [row - col], sums + [row + col])

位运算

该算法时间复杂度很高,所以当n超过32时,也不知道要算多久才能算出来

实践证明,32位数字足够用了

class Solution:    def totalNQueens(self, n: int) -> int:        self.res = 0        self.helper(n, 0, 0, 0, 0)        return self.res
def helper(self, n: int, row: int, cols: int, diffs:int, sums:int) -> None:
if row == n: self.res += 1 return
# (cols | diffs | sums) 三个方向取或,0就是没有占用的位置 # ~取反,1就是没有占用的位置, 但是32位的头部0也会变成1 # 所以, ((1 << n) - 1)只有后这些位置是有意义的。 candidate = ~(cols | diffs | sums) & ((1 << n) - 1)
while candidate > 0:
# 得到末尾的1(负数的表示正数取反+1), 获得放置位置 p = candidate & -candidate
# 往下递归时,列垂直向下, ↖️↘️往右移一位, ↙️↗️往左移一位 self.helper(n, row + 1, cols | p, (diffs | p) >> 1, (sums | p) << 1)
# 消掉末尾的1 candidate &= candidate - 1

耗时测试如下:

from typing import Listfrom collections import Counterfrom time import time
[答案代码块]
s = Solution()for i in range(100): start = time() res = s.totalNQueens(i) print('n=%s 耗时:%s, 结果%s' % (i, time() - start, res))
[console输出]n=0 耗时:2.1457672119140625e-06, 结果1n=1 耗时:5.0067901611328125e-06, 结果1n=2 耗时:4.76837158203125e-06, 结果0n=3 耗时:6.9141387939453125e-06, 结果0n=4 耗时:1.9073486328125e-05, 结果2n=5 耗时:5.316734313964844e-05, 结果10n=6 耗时:0.000179290771484375, 结果4n=7 耗时:0.0005168914794921875, 结果40n=8 耗时:0.0018699169158935547, 结果92n=9 耗时:0.008151054382324219, 结果352n=10 耗时:0.03539919853210449, 结果724n=11 耗时:0.15874195098876953, 结果2680n=12 耗时:0.8340210914611816, 结果14200n=13 耗时:4.572168827056885, 结果73712n=14 耗时:26.882348775863647, 结果365596n=15 耗时:185.4061300754547, 结果2279184n=16 耗时:1221.420109987259, 结果14772512...

--End--

本文分享自微信公众号 - 极客见闻(geekbro)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部