正确的数据结构来表示数独之谜？

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也是这样)。

这样可以很好地将细胞洗牌，从而产生一个很好的谜题。

然后，我开始选择随机的细胞，并将它们设置为未知。一旦一个细胞被设置为未知，我就把整个谜题传递给解谜者。如果它是可解的，我会继续，否则我会重新声明细胞和继续。

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

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

所以，对于数独初学者来说，这不是一件痛苦的事，我会让他们指定一个较低的难度，这样就可以把一定数量的不必要的细胞放回去。

不错的计划，也许会有更好的计划，但对我来说效果很好。

现在，如果我能搞清楚这件事，我就会幸福地死去:-)

Answer 2

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

Answer 3

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

我注意到，在大多数语言实现中，2D数组(任何被实现为“X数组”的数组)都需要额外的访问时间开销(对顶级数组的访问一次，子数组的第二次访问)。

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

您应该能够将1D数组访问隐藏在采用2D索引的setter和getter后面。如果您的语言具有这种能力(如果Python是这样的话，不知道)，那么这样的小方法可以内联以获得额外的速度。