数独解法学习，好像是递归剪枝了

aoe1981 · 发表于 2020-2-29 22:55

一言难尽，就放两张图：

新版自制“数独谜题难度等级表”.png

一个链接：

https://www.toutiao.com/i6798880895219532296/

和文中主要的猜测性结论：

1.基于四种基本的数独推断规则的递归格数最少是13格。

（重要程度★★★★★）

2.基于四种基本的数独推断规则的递归格数为62、63、64格的唯一解数独谜题不存在，换言之任意唯一解数独谜题的任意17提示格均能至少逻辑断定3个空单元格。

（重要程度★）

就这样吧。

yangyangzhifeng · 发表于 2020-3-1 11:20

aoe1981 发表于 2020-2-29 22:55
一言难尽，就放两张图：

区块的算法可以一次搞定1-9，提示如下：区块.PNG

黄，绿，红三区的候选数分区用Or得到a,bc三个数，如果d= (a and (b xor c))，d>0 则有区块删数存在，绿，红区的单元格候选数可以and not d，这样就实现了区块删减法

aoe1981 · 发表于 2020-3-1 11:27

yangyangzhifeng 发表于 2020-3-1 11:20
区块的算法可以一次搞定1-9，提示如下：

黄，绿，红三区的候选数分区用Or得到a,bc三个数，如果d= (a ...

高深，暂时不懂。若要进阶，必是要追寻大神的脚步啊……

yangyangzhifeng · 发表于 2020-3-1 11:55

aoe1981 发表于 2020-3-1 11:27
高深，暂时不懂。若要进阶，必是要追寻大神的脚步啊……

你的列，行，宫排除，其实是数独隐形唯一数技巧，Hidden Single；另外你的猜想不成立，因为递归顺序不一样，结论不一样，在数独来说有专门的术语，叫魔术格数量，Backdoor Size；已知标准数独，还没有找到魔术格数量多于3的题，也就是最多递归3次就够了

yangyangzhifeng · 发表于 2020-3-1 12:11

你测试这题，是单魔术格的题，猜中以下任意一格，题目瓦解
r2c2=1
r2c9=2
r3c1=2
r3c7=1
r4c1=1
r4c3=6
r5c4=6
r5c5=1
r6c7=2
r6c9=6
r7c1=6
r7c4=2
r7c9=1
r8c3=1
r8c5=6
r9c2=2
r9c4=1
r9c7=6

aoe1981 · 发表于 2020-3-1 12:22

本帖最后由 aoe1981 于 2020-3-1 12:33 编辑

yangyangzhifeng 发表于 2020-3-1 12:11
你测试这题，是单魔术格的题，猜中以下任意一格，题目瓦解
r2c2=1
r2c9=2

我对您所说的“魔术格”把握不是十分准确，但我感觉它就是我说的“试填格”或“递归格”，其候选数在2个到9个之间。

我觉得我们好像在讨论两条线上的问题。

我所指的“递归格”的数量仅仅针对初次遇到“递归盘面”（即所有空格的候选数均大于1，使用已知数独技巧排除后依然如此）时的所有空格的数量。的确，由于递归次序的不同，当试填一个数后，接下来可以“逻辑断定”的空格数量是不一样的。我由于掌握的数独技巧不多，导致最终递归的层数较多。

我理解您所说的“还没有找到魔术格数量多于3的题”，是不是指的是每次遇到“递归盘面”时的节点数（或者说是在一条递归路径上总共遇到“递归盘面”的次数，再或者说是整个解题过程中“猜的次数”），故而有“最多递归3次”的结果？

我是静态地在想问题：一个盘面状态中如果有9个空格，这9个空格肯定是可以被逻辑断定的（针对有唯一解的数独谜题），因为总是免不了“同数八缺一”或“同区八缺一”的情形的。

aoe1981 · 发表于 2020-3-1 12:45

yangyangzhifeng 发表于 2020-3-1 12:11
你测试这题，是单魔术格的题，猜中以下任意一格，题目瓦解
r2c2=1
r2c9=2

看来您指的是我发在微头条上的这道题：

微头条.png

也就是知乎上的哪道题：
https://zhuanlan.zhihu.com/p/39306130

解这道题，我递归了5层。您所说的“单魔术格”，是不是意味着最少只需递归一次即可完成此题？若是这样，说明更高级的数独技巧真的异常生猛！

yangyangzhifeng · 发表于 2020-3-1 13:00

......6.89....2.........3..5...6..7....8.........3.....2...75...381............4.
这题算多少格？

aoe1981 · 发表于 2020-3-1 13:30

本帖最后由 aoe1981 于 2020-3-1 13:53 编辑

yangyangzhifeng 发表于 2020-3-1 13:00
......6.89....2.........3..5...6..7....8.........3.....2...75...381............4.
这题算多少格？

感谢感谢，您帮我找到了递归格数64格的唯一解数独谜题，我的猜测2显然错了，我随机测试了好些日子，有些题都测重复了，总是找不出递归格64格的。现在，我会补充说明前面的结论错误的部分了，感谢感谢！

64格递归格.PNG

我的算法面对这道题递归了23层，效率明显变低了不少。这样的题应当保存下来作为算法的试金石。

佩服佩服。

aoe1981 · 发表于 2020-3-1 13:34

yangyangzhifeng 发表于 2020-3-1 13:00
......6.89....2.........3..5...6..7....8.........3.....2...75...381............4.
这题算多少格？

是不是各种初始盘面递归格的数量并不是均匀分布的，越是靠近两个极端，比如最多64格，最少13格左右（现在我都不敢确定这个结论一定是正确的），总是比较稀少的。在我的测试中，等级6、7、8总是最多出现的。

看来，我又得调整所谓“闹着玩”的“数独谜题难度等级表”了……呵呵

		自动登录	找回密码
密码			免费注册

[原创] 数独解法学习，好像是递归剪枝了

评分

评分

评分

评分