algorithm - 生成最小/不可简化的数独

Question

如果一个数独谜题有唯一解，那么它就是最小数独(也称为不可约数独)，但是删除任何数字都会产生一个有多个解的谜题。换句话说，每个数字都是确定解决方案所必需的。

我有一个生成最小数独的基本算法:

• 生成一个完整的拼图。
• 以随机顺序访问每个单元格。对于每个访问过的单元格:
  • 暂时去掉它的数字
  • 使用递归回溯算法解决难题两次。一个求解器按正序尝试数字 1-9，另一个按相反顺序尝试。从某种意义上说，求解器正在遍历包含所有可能配置的搜索树，但从两端开始。这意味着当且仅当拼图有唯一解，这两个解将匹配。
  • 如果谜题有唯一解，则永久删除该数字；否则，将其放回原处。

此方法可以保证产生最少的谜题，但速度很慢(在我的计算机上为 100 毫秒，在智能手机上为数秒)。我想减少解决的次数，但我能想到的所有显而易见的方法都是不正确的。例如:

• 添加数字而不是删除它们。这样做的好处是，由于最小谜题需要至少 17 个填充数字，因此前 17 个数字保证没有唯一的解决方案，从而减少了解决。不幸的是，由于以随机顺序访问单元格，因此将在“锁定”唯一解决方案的一个重要数字之前添加许多不必要的数字。例如，如果添加的前 9 个单元格都在同一列中，则那里有大量冗余信息。
• 如果没有其他数字可以替代当前数字，则保留它并且不解决难题。因为检查放置是否合法比解决难题两次快数千倍，这可能可以节省大量时间。但是，现在没有其他合法数字并不意味着以后不会有，一旦我们删除其他数字。
• 由于我们生成了原始解决方案，因此对每个单元格仅求解一次并查看它是否与原始解决方案匹配。这不起作用，因为原始解决方案可能位于可能解决方案的搜索树中的任何位置.例如，如果原始解决方案靠近树的“左侧”，而我们从左侧开始搜索，我们将错过树右侧的解决方案。

我还想优化求解算法本身。困难的部分是确定解决方案是否唯一。我可以进行微优化，例如为每个单元格创建合法布局的位掩码，如 this wonderful post 中所述。 .但是，更高级的算法(如 Dancing Links 或模拟退火)并非旨在确定唯一性，而是旨在找到任何解决方案。

如何优化我的最小数独生成器？

Answer 1

我有一个想法关于第二个选项 如果您为第一个 17 个数字添加 3 个额外检查，您的建议会更好

• 找出 1-9 之间的 17 个随机数的列表

• 在提供的随机位置添加每个项目

  1. 添加的这些新数字不符合数独的 3 个基本标准

     • 同一行没有相同的数字
     • 同一列中没有相同的数字
     • 同一个3x3矩阵中没有相同的数

  2. 如果条件 1 失败，则移至下一列或行并再次检查 3 个基本条件。

  3. 如果没有下一行(即第 9 列或第 9 行)添加到第 1 列填满 17 个字符后，运行您的求解器逻辑并寻找您的独特解决方案。