创建十六进制洪水拼图的算法

Question

我正在创建一款益智游戏，虽然可以手动玩简单的关卡，但要通过计算机程序来解决更难的关卡。拼图是六角板上的洪水填充。你可以试试样机here .

_{(来源:hacker.org)}

拼图的工作原理如下:通过从顶部选择一种颜色，您可以从左上角的图 block 开始进行整体填充。这逐渐将板转换为纯色。挑战是在一定数量的 Action 中做到这一点。

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

我面临的问题是，当我尝试这种方法时，我的上限太高了。在这个移动次数内解决难题变得微不足道，即使是随机移动也是如此。

一种不是解决方案的方法是生成一个随机板，然后对其进行最优求解并将其设置为目标。重点是创建一个难题，其中最佳解决方案是 NP 时间或至少是一个困难的 P。

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

Answer 1

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

我的建议是一样的。尝试找到使拼图很有可能具有所需属性的条件，并针对这些条件进行测试。或者，您可以使用遗传算法/神经网络并训练它们识别“好”的谜题，这其实是一回事。