此问题不仅限于数独,还可以包括Kakuro,Hitori,Nurikabe等。
我了解数独和其他类似难题的算法,但我很难确定如何创建。说我想要一个Sudoku生成器(使用最受欢迎的)。我想它需要分两个步骤工作:
删除解决方案的某些部分,以确保只删除多余的部分,这也不是小事。
是否有通用算法可以解决?我该如何实施这样的事情?
我知道我的问题是“广泛的”,到目前为止,我并没有显示很多(将问题分成两部分),但是我没有任何线索可以开始考虑该算法。我不是在寻求解决方案,而是在寻求有关如何开始的提示。
此问题不仅限于数独,还可能包括Kakuro,Hitori,Nurikabe等。我了解解决数独和其他类似难题的算法,但我很难弄清楚...]]] >>
定义一组可以帮助人类进行游戏的规则。例如,在数独中,这些规则之一可能是:
假设程序应该生成给定难度的数独。我们将解释为这意味着要解决数独问题,将要求玩家至少使用一次至少具有该难度的规则或从未预见到的奇特规则。
现在从已解决的数独开始。随机删除50%的值。检查数独是否可以仅使用难度范围内的已知规则来解决。如果不是,请恢复已删除细胞的25%,然后重复。如果可以解决,请再随机去除25%的细胞。像二进制搜索算法一样,继续将涉及的单元格数量减半(恢复它们或删除它们),直到到达搜索结束为止。对于Sudoku游戏,此过程大约需要进行7次迭代。然后,您将拥有一种“局部最小值”,可以在其中应用规则来求解。
这远非完美,因为很可能还有一些其他单元可以清除,同时仍然允许规则朝着解决方案努力。因此,如果您想优化此搜索,则可以添加一些其他迭代以删除随机单元,只要仍然可以通过应用规则来解决结果板。