用什么样的数据结构来表示数独谜题比较合适？

Question

什么是表示数独谜题的智能数据结构？即一个9x9的正方形，每个“单元格”包含数字或空白。

特别考虑以下几点：

• 可以跨行、列和3x3“组”进行比较
• 易于实现（特别是在Python中）
• 效率（不是关键因素）

我想，在紧急情况下，2D数组可能会起作用，但这似乎不是一种优雅的解决方案。我只是想知道是否有更好的数据结构。

- Rafe Kettler

Answer 1

实际上，我建了这样一个“野兽”，既是求解器又是生成器，使用了一个二维数组。它运行良好。

你只需要理解索引以及它们的位置，这并不难掌握。

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

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

-------------------------------------------

如果你感兴趣，可以了解一下我在求解器/生成器中使用的算法。

首先，我编写了求解器部分，它会首先将所有单元格设置为可以是任何值，然后按顺序应用所有规则，以查看是否可以解决或限制个别单元格，比如：

- 如果单元格是提示中的特定值，则将其设置为该值。 - 如果在行（或列或小方块）中仅剩下一个单元格，您可以将其设置为剩余的值。 - 如果一个单元格被标记为可能是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的东西，我就能开心地死去了 :-)

- paxdiablo

---

只要你需要进行特殊检查（比如在3x3组中），你可以很好地针对2D数组编写代码。 - Ira Baxter

Answer 2

阅读彼得·诺维格的文章解决每个数独难题。在这个过程中，您很可能会学习一些关于数据结构、Python和性能分析的新知识，并且不太可能找到更优雅的解决方案。

- Ned Deily

---

哇...真是太棒了。我并不特别喜欢数独，但我认为我需要沉淀一下Norvig的写作。我喜欢他这样做是为了试图治愈他妻子的瘾症。 :-) - Peter Rowell

Answer 3

其他人已经合理地建议使用2D数组。

我注意到，在大多数语言实现中，“数组的数组X”遭受额外的访问时间开销（一次访问顶层数组，第二次访问子数组）。

我建议您将数据结构抽象地实现为2D数组（甚至可以继续使用2个索引），但将数组实现为单个81个单元的块，经典地由i * 9 + j索引。这给您概念上的清晰度，并通过避免第二个内存访问而实现了更高效的实现。

您应该能够将1D数组访问隐藏在采用2D索引的setter和getter后面。如果您的语言具有此功能（不知道Python是否如此），这些小方法可以进行内联以获得额外的速度。

- Ira Baxter

Answer 4

Python在数据结构方面并不多。你最好的选择可能是使用普通的2D数组或者使用类来构建自己的数据结构。

你可以在这里了解更多关于Python数据类型的信息。

- Joshkunz