创建十六进制洪水难题的算法

Question

我正在创建一个益智游戏，虽然可以通过简单的级别手动播放，但意味着要通过计算机程序解决难题。这个难题是在六角板上填满水。你可以尝试一个原型here。

alt text http://www.hacker.org/flood/screen.png

这里是难题是如何工作的：通过从顶部的颜色，你执行倾倒填充从左上角开始瓦。这逐渐将电路板转换为纯色。挑战在于在一定程度上做到这一点。

我创建类似这样的几个难题，关键是使用产生很难不知道它们是如何创建解决板的算法。例如，在这里我们可以通过颠倒填充来制作一块板子：从一块坚硬的板子向后工作直到它没有被淹没。我们知道采取了多少步骤，并且可以将此设置为解决方案的下限。

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

的一种方法，是不是一个解决方案是产生一个随机板，然后最佳解决它和设置此作为目标。问题的关键是建立一个谜，其中解决它最佳的NP时间或至少是一个硬P.

所以，我正在寻找的是在那里解决这些问题，因为他们得到更大的，可以产生非常硬板用的算法，成为一个严峻的挑战。

Answer 1

在做RSA加密，我们没有发现的素数，我们选择随机编号，然后测试他们给我们的数量是首要的越来越高的概率，withou不断证明它。

我建议一样的。试着找出那些具有所需特性的难题的可能性，并对其进行测试。或者你可以使用遗传算法/神经网络，并训练他们认识到“好”的难题，这相当于同样的事情。

Answer 2

我会试图证明它是一个NP完全或P，来感受一下这是很难的配置。

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

Answer 3

我打过矩形洪水拼图很多（http://labpixies.com/gadget_page.php?id=10）。兴奋地看到一个Hex版本！我认为找到一场艰苦的比赛非常简单：避免在拼图中出现相同颜色的大块。至少在我见过的矩形案例中，几乎所有可以通过少量步骤解决的难题都有很大的色块。

P.S.我认为你的“下限”是无效的。在工作时，如果使用了一个好的策略，你可以用更少的步骤完成。 “下限”确实是最佳解决方案的上限。