我正在创建一个谜题游戏,容易级别可以手动玩,但更难的级别需要计算机程序来解决。这个谜题是在六边形棋盘上进行的泛洪填充。你可以在这里尝试一个原型here。
一种不是解决方案的方法是生成一个随机的板子,然后最优地解决它,并将其设置为目标。重点是创建一个拼图,其中最优解的解决时间是NP时间或至少是困难的P。
所以我要找的是一种算法,可以生成极难的板子,在解决它们变得更加困难的情况下。
(来源:hacker.org)
这个谜题的工作方式如下:从顶部选择一种颜色,从左上角开始进行泛洪填充。这会逐步将棋盘转换为单一的颜色。挑战在于在规定的步数内完成。
我已经创建了几个类似的谜题,关键在于使用一种算法生成难以解决的棋盘,而不知道它们是如何创建的。例如,在这里我们可以通过反向泛洪填充来生成一个棋盘:从一个实心的棋盘向后工作,直到它被取消填充。我们知道这需要多少步骤,并将其设置为解决方案的下限。
我面临的问题是,当我尝试这种方法时,我的上限太高了。即使随机移动,也很容易在这个步数内解决拼图。一种不是解决方案的方法是生成一个随机的板子,然后最优地解决它,并将其设置为目标。重点是创建一个拼图,其中最优解的解决时间是NP时间或至少是困难的P。
所以我要找的是一种算法,可以生成极难的板子,在解决它们变得更加困难的情况下。