正确的数据结构来表示数独游戏?

实际上,我建立了这样一个野兽,一个解算器和一个生成器,我使用了一个二维数组。它工作得很好。

行中单元格之间的相对关系不会因列的不同而改变,列中单元格甚至小正方形中的单元格也是如此。

有时候,一个不那么“优雅”的解决方案就行了。事实上,有时候,它更可取:-)

就其价值而言,您可能对我用于解算器/生成器的算法感兴趣。

首先我编写了解算器部分,它首先将所有单元格设置为可以是任何值,然后依次应用所有规则,以查看单个单元格是否可以被解算或受到其他限制,例如:

• 如果该单元格是线索中的特定值,请将其设置为该值。
• 如果一行(或列或小正方形)中只剩下一个单元格,则可以将其设置为剩余值。
• 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

这使细胞重新排列,足以产生一个像样的拼图。

这让我无法得到一个逻辑上无法解决的谜题。

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

所以,对于数独初学者来说,这并不痛苦,我会允许他们指定一个较低的难度级别,将一定数量的不必要的细胞放回去。

不错的计划,也许有更好的,但那一个对我很好。

现在,如果我能搞清楚这些卡库罗的东西,我会高兴死的:-)

阅读 Peter Norvig Solving Every Sudoku Puzzle . 您不太可能找到一个更优雅的解决方案,而且您可能会在这个过程中学到一些关于数据结构、Python和性能分析的新知识。

我注意到,在大多数语言实现中,2D数组(实现为“X数组数组”的任何东西)都会遭受额外的访问时间开销(一次访问顶级数组,一次访问子数组)。

您应该能够在接受2D索引的setter和getter后面隐藏1D数组访问。如果您的语言具有这种能力(如果Python是这样的,则不需要),那么可以内联这样的小方法以提高速度。

Python在数据结构方面没有太多的功能。你最好的选择可能只是一个普通的2D数组或者使用类来构建你自己的数组。

here .