创建六角形洪水拼图的算法

Question

我正在制作一款益智游戏，虽然可以手动播放以获得简单的等级，但是可以通过计算机程序来解决更难的游戏。拼图是六角形板上的洪水填充。你可以尝试一下原型here。

（来源：hacker.org）

拼图的工作原理如下：通过从顶部选择颜色，您可以从左上角的拼贴开始执行填充。这逐渐将电路板转换为纯色。挑战是在一定数量的举动中做到这一点。

我已经创建了几个与此类似的谜题，关键是要使用一种算法来生成难以解决的板，而不知道它们是如何创建的。例如，在这里我们可以通过反转洪水填充来生产板：从实心板向后工作直到它被解开。我们知道这需要多少步骤，并且可以将其设置为解决方案的下限。

我面临的问题是，当我尝试这种方法时，我的上限太高了。即使通过随机移动，在这些移动中解决难题变得微不足道。

一种不是解决方案的方法是生成随机板，然后以最佳方式求解并将其设置为目标。重点是创造一个拼图，最佳地解决它是NP时间或至少是一个硬P.

所以我正在寻找的是一种算法，可以生成极其坚硬的板，解决它们，随着它们变大，成为一个严峻的挑战。

Answer 1

在进行RSA加密时，我们找不到素数，我们选择随机数，然后对它们进行测试，这使得我们越来越有可能将数字作为素数，而不是证明它。

我建议一样。尝试找到能够提供具有所需属性的拼图的良好可能性的条件，并对其进行测试。或者你可以使用遗传算法/神经网络训练他们识别“好”的谜题，这相当于同样的事情。

Answer 2

我会尝试证明它是NP完全的或在P中，以了解难以配置的配置。

我还抽象出六边形并使用表示作为图形。

Answer 3

我玩了很多矩形洪水拼图（http://labpixies.com/gadget_page.php?id=10）。兴奋地看到Hex版本！我认为找到一款简单的游戏很容易：避免在拼图中出现相同颜色的大块。至少在我见过的矩形情况下，几乎所有可以通过少量步骤解决的谜题都有大块颜色。

附：我认为你的“下限”是无效的。在向前工作时，如果使用了一个好的策略，你实际上可以用更少的步骤完成。 “下限”实际上是最优解的上限。