如果数独谜题具有唯一解，则它是最小的（也称为不可约解），但删除任何数字都会产生具有多个解的谜题。换句话说，每个数字都是确定解决方案所必需的。
我有一个生成最小数独的基本算法：
- 生成一个完整的谜题。
- 以随机顺序访问每个单元格。对于每个访问的单元格：
- 暂时去掉它的数字
- 使用递归回溯算法两次解决难题。一个求解器以正序尝试数字 1-9，另一个以相反的顺序尝试。从某种意义上说，求解器正在遍历包含所有可能配置的搜索树，但来自相反的两端。这意味着如果拼图有唯一解，则这两个解将匹配。
- 如果谜题有唯一解，则永久删除该数字；否则，将其放回原处。
这种方法可以保证产生一个最小的谜题，但它很慢（我的电脑上 100 毫秒，智能手机上几秒钟）。我想减少解决的次数，但我能想到的所有明显方法都是不正确的。例如：
- 添加数字而不是删除它们。 这样做的好处是，由于最小的谜题至少需要 17 个填充数字，所以前 17 个数字保证没有唯一的解决方案，减少了解决的数量。不幸的是，由于单元格是按随机顺序访问的，因此会在“锁定”唯一解决方案的一个重要数字之前添加许多不必要的数字。例如，如果添加的前 9 个单元格都在同一列中，则那里有大量冗余信息。
- 如果没有其他数字可以替代当前的数字，请将其保留，不要解决难题。因为检查一个展示位置是否合法比解决两次难题要快数千倍，这可以节省大量时间。但是，仅仅因为现在没有其他合法数字并不意味着一旦我们删除其他数字就不会再有。
- 由于我们生成了原始解决方案，因此每个单元格只解决一次，看看它是否与原始解决方案匹配。这不起作用，因为原始解决方案可能位于可能解决方案的搜索树中的任何位置。例如，如果原始解决方案靠近树的“左侧”，并且我们从左侧开始搜索，我们将错过树右侧的解决方案。
我还想优化求解算法本身。困难的部分是确定解决方案是否是唯一的。我可以进行微优化，例如为每个单元格创建合法位置的位掩码，如这篇精彩的帖子中所述。然而，更高级的算法，如 Dancing Links 或模拟退火，并非旨在确定唯一性，而只是为了找到任何解决方案。
如何优化我的最小数独生成器？