創建十六進制洪水難題的算法

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.我認爲你的「下限」是無效的。在工作時，如果使用了一個好的策略，你可以用更少的步驟完成。 「下限」確實是最佳解決方案的上限。