algorithm - 如何使用独特的解决方案生成数独板

Question

如何用独特的解决方案生成数独板？我的想法是初始化一个随机板，然后删除一些数字。但我的问题是如何保持解决方案的唯一性？

Answer 1

这是我自己的 SuDoKu 程序的实现方式:

<小时/>

1. 从一个完整、有效的棋盘开始(包含 81 个数字)。

2. 列出所有 81 个单元格位置并随机打乱顺序。

3. 只要列表不为空，就从列表中取出下一个位置，并从相关单元格中删除该数字。

4. 使用快速回溯求解器测试唯一性。理论上，我的求解器能够计算所有解决方案，但为了测试唯一性，当它找到多个解决方案时，它会立即停止。

5. 如果当前板仍然只有一个解，则转到步骤 3) 并重复。

6. 如果当前棋盘有多个解决方案，则撤消最后的删除操作(第 3 步)，然后继续第 3 步处理列表中的下一个位置

7. 测试完所有 81 个位置后停止。

<小时/>

这不仅为您提供了独特的棋盘，而且还为您提供了在不破坏解决方案的独特性的情况下无法删除更多数字的棋盘。

当然，这只是算法的后半部分。前半部分是首先找到一个完整的有效板(随机填充!)它的工作原理非常相似，但是“在另一个方向”:

<小时/>

1. 从一个空板开始。

2. 在其中一个空闲单元格中添加一个随机数字(该单元格是随机选择的，并且该数字是根据 SuDoKu 规则从对该单元格有效的数字列表中随机选择的)。

3. 使用回溯求解器检查当前棋盘是否至少有一个有效的解。如果不是，请撤消步骤 2 并使用另一个号码和单元格重复。请注意，此步骤可能会自行生成完整的有效板，但这些板绝不是随机的。

4. 重复直到板上完全填满数字。