6

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

特殊考虑包括：

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

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

4

4 回答 4

11

实际上，我构建了这样一个野兽，既是求解器又是生成器，并且我使用了 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 的东西，我会快乐地死去 :-)

于 2010-11-01T01:20:36.267 回答
7

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

于 2010-11-01T03:45:36.530 回答
2

其他人合理地建议简单地使用二维数组。

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

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

您应该能够将 1D 数组访问隐藏在采用 2D 索引的 setter 和 getter 后面。如果您的语言有能力（不知道这是否适用于 Python），那么可以内联这些小方法以提高速度。

于 2010-11-01T01:42:29.980 回答
0

Python 没有太多的数据结构方式。您最好的选择可能只是一个常规的 2D 数组或使用类构建您自己的数组。

您可以在此处阅读有关 python 数据类型的更多信息。

于 2010-11-01T01:23:57.073 回答