适当的数据结构代表数独谜题？

Question

什么是用于表示数独谜题的智能数据结构？即9X9平方,其中每个"单元格"包含数字或空白.

特别考虑包括:

• 能够跨行,列和3X3"组进行比较
• 易于实现(特别是在Python中)
• 效率(不是最重要的)

我想在一个紧凑的情况下,2D阵列可能会起作用,但这似乎不是一个优雅的解决方案.我只是想知道是否有更好的数据结构.

Answer 1

实际上,我构建了这样一个野兽,无论是解算器还是生成器,我都使用了2D阵列.它工作正常.

您只需要了解索引及其位置,并且不难掌握.

一行中的单元格之间的相对关系不会根据列而改变,对于列中的单元格也是如此,或者甚至是迷你方形中的单元格.

有时,一个不那么"优雅"的解决方案就好了.事实上,有时,它更可取:-)

对于它的价值,您可能对我用于求解器/生成器的算法感兴趣.

首先,我编写了求解器部分,它首先将所有单元格设置为能够为任何值,然后按顺序应用所有规则,以查看单个单元格是否可以被解决或以其他方式限制,例如:

• 如果单元格是线索中的特定值,请将其设置为该值.
• 如果一行(或列或迷你方)中只剩下一个单元格,则可以将其设置为剩余值.
• 如果一个单元格被标记为可能N并且N存在于其他地方的行/列/小方块中,则删除该可能性.
• 如果行/列/迷你方形中有两个单元格,并且它们具有相同的两种可能性(并且没有其他可能性),则该行/列/迷你方形中的所有其他单元格应该删除该可能性.

等等,添加我用于解决真实谜题的每条规则.

对于发电机,我开始:

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

然后,在不同大小(至少500)的循环中,继续交换行和列,使其永远不会产生无效的拼图.换句话说,将行或列与它们所在的组交换(例如,第1,2和3行是一个组,第4,5和6列也是如此).

这使得细胞足够好,可以产生一个像样的谜题.

然后,我开始选择随机单元格并将其设置为未知.一旦将一个单元格设置为未知,我就会将整个拼图传递给解算器.如果它是可以解决的,我会继续,否则我会重新启动细胞并继续.

这使我无法获得逻辑上无法解决的难题.

一旦完成了大量的随机单元删除,我将尝试使用相同的方法按顺序删除所有剩余的单元格.剩下的就是解决这个难题所需的最少信息量.

而且,对于数独初学者来说,这不是一个痛苦,我会允许他们指定一个较低的难度级别,这将使一定数量的不必要的单元格重新进入.

不是一个糟糕的计划,可能有更好的计划,但一个工作对我来说很好.

现在,如果我只能弄清楚这个Kakuro的东西,我会很高兴:-)

Answer 2

阅读Peter Norvig撰写的解决每个数独谜题的文章.您不太可能找到更优雅的解决方案,并且您可能会在此过程中学习有关数据结构,Python和性能分析的一些新内容.