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

Question

什么样的智能数据结构可以用来表示数独游戏？一、 一个9X9的正方形，其中每个“单元格”包含一个数字或一个空白。

特别注意事项包括：

• 能够跨行、列和3X3“组进行比较
• 易于实现（特别是在Python中）
• 效率（不是最重要的）

我想在紧要关头，2D数组可能可以工作，但这似乎不是一个优雅的解决方案。我只想知道是否有更好的数据结构。

Answer 1

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

Answer 2

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

你只需要了解索引和它们在哪里，这并不难掌握。

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

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

---

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

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

• 如果该单元格是线索中的特定值，请将其设置为该值。
• 如果一行（或列或小正方形）中只剩下一个单元格，则可以将其设置为剩余值。
• 如果单元格被标记为可能存在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也是）。

这将细胞重组得足够好，可以产生一个像样的拼图。

然后，我开始选择随机单元格并将它们设置为未知。一旦一个单元格被设置为未知，我就会把整个谜题传递给解算器。如果可以解决，我会继续，否则我会重新安装细胞并继续。

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

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

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

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

现在，如果我能搞清楚卡库罗的事，我会高兴死的：-）

Answer 3

其他人合理地建议简单地使用2D数组。

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

我建议您将数据结构抽象地实现为2D数组（甚至可能继续使用2个索引），但将数组实现为81个单元的单个块，由I*9+j进行经典索引。这样可以避免第二次内存访问，从而使概念更清晰，实现效率更高。

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