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