表示数独难题的合适数据结构？
要表示一个数独谜题，什么样的数据结构比较好呢？也就是说，我们需要一个9X9的方格，每个“单元格”里要么是一个数字，要么是空白。
在考虑这个问题时，有几个特别的方面：
- 需要能够比较同一行、同一列，以及3X3的小组里的数字
- 实现起来要简单（特别是在Python中）
- 效率不是最重要的
我想如果急需的话，使用一个二维数组也许可以，但这似乎不是一个很优雅的解决方案。我只是想知道有没有更好的数据结构。
4 个回答
其他人合理地建议可以直接使用二维数组。
我注意到，在大多数编程语言中，二维数组通常是以“数组的数组”的形式实现的，这样会导致额外的访问时间开销（你需要先访问顶层数组，再访问子数组）。
我建议你可以把数据结构抽象成一个二维数组（甚至可以继续使用两个索引），但实际上把这个数组实现为一个包含81个单元的单一块区域，索引方式可以用i*9+j来计算。这种做法让你在概念上更清晰，同时也能提高效率，因为这样就避免了第二次内存访问。
你可以通过设置器和获取器来隐藏一维数组的访问，这些方法可以接受二维索引。如果你的编程语言支持这种功能（我不确定Python是否支持），那么这些小方法可以被内联，以提高速度。
其实，我做过这样的东西，既是一个解题器也是一个生成器，我用了一个二维数组。效果很好。
你只需要理解一下索引的位置，这个不难掌握。
在同一行的单元格之间的相对关系不管在哪一列都是一样的，列也是如此，甚至在小方块里的单元格也是。
有时候，解决问题的方法不需要太“优雅”，其实这样也挺好，有时候甚至更好 :-)
如果你感兴趣的话，我可以分享一下我用来解题和生成的算法。
首先，我写了一个解题的部分，开始时把所有单元格都设为可以是任何值，然后按照规则一步步去看某个单元格能否被解出或者限制住，像这样的规则：
- 如果这个单元格在提示中是一个特定的值，就把它设为那个值。
- 如果在一行（或一列或一个小方块）只剩下一个单元格，你可以把它设为剩下的那个值。
- 如果一个单元格被标记为可能是
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的东西，我就可以心满意足地去死了 :-)