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