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

问题描述 投票:6回答:3

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

alt text (来源:hacker.org

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

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

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

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

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

algorithm hex puzzle flood-fill
3个回答
1
投票

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

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


1
投票

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

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


1
投票

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

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

© www.soinside.com 2019 - 2024. All rights reserved.