栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

数独回溯算法

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数独回溯算法

在仅用一种选择填充方块与在板上完全递归之间,您可以执行更多高级操作。让我们以“区域”为一行,一列或一个正方形区域(3x3或4x4)。

策略1

如果某个区域中只能有相同的K个数的K个正方形(例如,两个正方形只能取2、5,或者三个正方形只能取1、7和8),则该区域中的所有其他正方形可以’取那些具体的数字。您需要对每个区域进行迭代以淘汰“已取”的数字,因此您可以找到一个只有一个逻辑选择的正方形(例如,逻辑上带有2、4和5的第三个正方形只能取4,或者第四个带有1,3的正方形,
7和8在逻辑上只能取3)。

如果考虑以下示例,则必须通过迭代来解决。一个区域具有以下可能的正方形:

A:1 2 3
B:2 3
C:2 3 4 5
D:4 5
E:4 5

该算法应检测到正方形D和E拥有数字4和5,因此将4和5从区域中的其他正方形中排除。然后,该算法检测到正方形B和C拥有数字2和3,因此将它们从其他正方形中排除。这样,正方形A仅保留数字1。

策略2

如果仅在一个正方形中的区域中出现一个数字,则从逻辑上讲该正方形将保留该数字。

策略3

战术1和2只是战术3的特殊情况,只有具有K个相同数字的K个平方。您可以有K个平方和一组K个数字,并且这些K个平方可以容纳这些K个数字的任何子集。考虑以下区域示例:

A:1 2
B:2 3
C:1 3
D:1 2 3 4

正方形A,B和C只能容纳数字1、2和3。K代表K。这意味着任何其他正方形在逻辑上都不能容纳这些数字,使得正方形D仅具有数字4。

当K = N-1时,策略2是策略3的特例。

策略4

利用区域重叠。假设某个数字只能存在于该区域的某些正方形中。如果所有那些正方形都属于另一个重叠区域,则该数字应从该另一个区域中的所有其他正方形中排除。

策略5

缓存结果。所有区域都应具有“脏”标志,该标志表示该区域中的某些内容自上次处理该区域以来已发生更改。您无需处理未设置此标志的区域。


人类会使用所有这些策略,并且非常讨厌猜测数字,因为回溯确实是一个痛苦。实际上,董事会的难易程度是用解决董事会所需的最少猜测量来衡量的。对于大多数“极致”板,一个很好的猜测就足够了。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375197.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号