如果数独谜题具有独特的解决方案，那么它是最小的（也称为不可约），但是删除任何数字将产生具有多种解决方案的谜题。换句话说，每个数字都是确定解决方案所必需的。

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

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

这种方法可以保证产生最小的困惑，但它相当慢（在我的计算机上为100毫秒，在智能手机上为数秒）。我想减少求解的次数，但是我能想到的所有显而易见的方法都是不正确的。例如：

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

我还想优化求解算法本身。困难的部分是确定解决方案是否唯一。我可以进行微优化，例如为每个单元格创建合法放置的位掩码，如本精彩文章所述。但是，更先进的算法（如“跳舞链接”或模拟退火）并非旨在确定唯一性，而只是为了找到 任何 解决方案。

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