生成最小/不可还原的数独
如果数独谜题具有独特的解决方案，那么它是最小的（也称为不可约），但是删除任何数字将产生具有多种解决方案的谜题。换句话说，每个数字都是确定解决方案所必需的。
我有一个基本算法来生成最小的数独：
- 生成一个完整的难题。
- 随机访问每个单元。对于每个访问的单元格：
- 暂时删除其数字
- 使用递归回溯算法解决难题两次。一个求解器以正序尝试数字1-9，另一个以相反的顺序尝试。从某种意义上说，求解器正在遍历包含所有可能配置的搜索树，但从相反的一端开始。这意味着 ，则 。
- 如果拼图有独特的解决方案，请永久删除数字；否则，请放回去。
这种方法可以保证产生最小的困惑，但它相当慢（在我的计算机上为100毫秒，在智能手机上为数秒）。我想减少求解的次数，但是我能想到的所有显而易见的方法都是不正确的。例如：
- 这样做的好处是，由于最小的拼图需要至少17个填充数字，因此可以保证前17个数字没有唯一的解，从而减少了求解的数量。不幸的是，由于以随机顺序访问单元，因此将在“锁定”唯一解决方案的一个重要数字之前添加许多不必要的数字。例如，如果添加的前9个单元格都在同一列中，那么那里会有很多冗余信息。
- 因为检查安置是否合法比两次解决难题快数千倍，所以这可能会节省大量时间。但是，仅仅因为现在没有其他合法数字并不意味着以后我们删除其他数字也就不会再有其他合法数字了。
- 这不起作用，因为原始解决方案可能在可能解决方案的搜索树中的任何位置。例如，如果原始解位于树的“左侧”附近，而我们从左侧开始搜索，则将错过树右侧的解。
我还想优化求解算法本身。困难的部分是确定解决方案是否唯一。我可以进行微优化，例如为每个单元格创建合法放置的位掩码，如本精彩文章所述。但是，更先进的算法（如“跳舞链接”或模拟退火）并非旨在确定唯一性，而只是为了找到 任何 解决方案。
回答：
这是我实现的（高度近似）速度提高百分比的主要优化：
- 使用位掩码跟踪每个单元格中满足哪些约束（行，列，框）。这样可以更快地查找某个放置位置是否合法，但是放置位置则较慢。生成带有位掩码的难题而不只是解决难题的一个复杂因素是，可能必须删除数字，这意味着您需要将三种约束类型作为不同的位进行跟踪。进一步的优化是将每个数字和每个约束的掩码保存在数组中。
- 如果生成时间太长，请暂停生成并重新启动。最佳策略是增加每次失败生成后的超时时间，以减少无限期继续运行的机会。 ，主要来自减少最坏情况的运行时间。
- mbeckish和user295691的建议（请参阅原始帖子的评论）。
以上是 生成最小/不可还原的数独 的全部内容， 来源链接： utcz.com/qa/398272.html
