假如你对数独解法感兴趣,你可能听说过精确覆盖问题。给定全集 X 和 X 的子集的集合 Y ,存在一个 Y 的子集 Y*,使得 Y* 构成 X 的一种分割。
这儿有个Python写的例子。
X = {1, 2, 3, 4, 5, 6, 7} Y = { 'A': [1, 4, 7], 'B': [1, 4], 'C': [4, 5, 7], 'D': [3, 5, 6], 'E': [2, 3, 6, 7], 'F': [2, 7]}
这个例子的唯一解是['B', 'D', 'F']。
精确覆盖问题是NP完备(译注:指没有任何一个够快的方法可以在合理的时间内,意即多项式时间 找到答案)。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链,使用双向链表来表示该问题的矩阵。
然而,舞蹈链实现起来可能相当繁琐,并且不易写地正确。接下来就是展示Python奇迹的时刻了!有天我决定用Python来编写X 算法,并且我想出了一个有趣的舞蹈链变种。
算法
主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了 Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表,换句话说就是能从列中快速访问行元素。为实现这个目的,我们把X转换为字典。在上述的例子中,它应该写为
X = { 1: {'A', 'B'}, 2: {'E', 'F'}, 3: {'D', 'E'}, 4: {'A', 'B', 'C'}, 5: {'C', 'D'}, 6: {'D', 'E'}, 7: {'A', 'C', 'E', 'F'}}
眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上,我们需要能快速删除和添加行到每列,这就是为什么我们使用集合。另一方面,高德纳没有提到这点,实际上整个算法中所有行是保持不变的。
以下是算法的代码。
def solve(X, Y, solution=[]): if not X: yield list(solution) else: c = min(X, key=lambda c: len(X[c])) for r in list(X[c]): solution.append(r) cols = select(X, Y, r) for s in solve(X, Y, solution): yield s deselect(X, Y, r, cols) solution.pop() def select(X, Y, r): cols = [] for j in Y[r]: for i in X[j]: for k in Y[i]: if k != j: X[k].remove(i) cols.append(X.pop(j)) return cols def deselect(X, Y, r, cols): for j in reversed(Y[r]): X[j] = cols.pop() for i in X[j]: for k in Y[i]: if k != j: X[k].add(i)
真的只有 30 行!
格式化输入
在解决实际问题前,我们需要将输入转换为上面描述的格式。可以这样简单处理
X = {j: set(filter(lambda i: j in Y[i], Y)) for j in X}
但这样太慢了。假如设 X 大小为 m,Y 的大小为 n,则迭代次数为 m*n。在这例子中的数独格子大小为 N,那需要 N^5 次。我们有更好的办法。
X = {j: set() for j in X} for i in Y: for j in Y[i]: X[j].add(i)
这还是 O(m*n) 的复杂度,但是是最坏情况。平均情况下它的性能会好很多,因为它不需要遍历所有的空格位。在数独的例子中,矩阵中每行恰好有 4 个条目,无论大小,因此它有N^3的复杂度。
优点
- 简单: 不需要构造复杂的数据结构,所有用到的结构Python都有提供。
- 可读性: 上述第一个例子是直接从Wikipedia上的范例直接转录下来的!
- 灵活性: 可以很简单得扩展来解决数独。
求解数独
我们需要做的就是把数独描述成精确覆盖问题。这里有完整的数独解法代码,它能处理任意大小,3×3,5×5,即使是2×3,所有代码少于100行,并包含doctest!(感谢Winfried Plappert 和 David Goodger的评论和建议)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 《原神》「星路拾忆」网页活动壁纸展示
- 群星.2024-祝你幸福!电影原声带【阿里巴巴】【FLAC分轨】
- 于台烟.2004-执着【乾坤唱片】【WAV+CUE】
- 黄品源.2004-感谢·情人(引进版)【滚石】【WAV+CUE】
- 《最终幻想16》评测:游、戏两难全的系列转折
- 《纸嫁衣》五部打包¥104,《鬼泣5》仅需¥44
- 《崩坏:星穹铁道》造物大赛卷出新高度
- 《王菲 菲常传奇 2CD》[WAV+CUE][950MB]
- 《王菲 空灵独味唱腔 非常传奇 紫水晶2CD》[WAV+CUE][860MB]
- 《车载专业测试王1号 极品音质》[WAV/分轨][980MB]
- 炉石传说的国服回归送什么奖励 炉石传说9.25回归最新消息介绍
- 云顶之弈最强阵容汇总2024 云顶之弈最强阵容搭配最新版本
- S14lol全球总决赛在哪观看 lol全球总决赛观赛直播地址汇总
- 黄思婷2011-感谢天[豪记唱片][WAV+CUE]
- 孙淑媚2013-太阳[台湾首版][WAV+CUE]