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

Question

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

替代文字http://www.hacker.org/flood/screen.png

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

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

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

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

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

Answer 1

在进行 RSA 加密时，我们找不到素数，而是选择随机数，然后对其进行测试，从而使该数字成为素数的概率越来越高，而无需证明。

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