algorithm - ヘックス フラッド パズルを作成するアルゴリズム

Question

簡単なレベルでは手でプレイできますが、難しいレベルではコンピューター プログラムで解決することを意図したパズル ゲームを作成しています。パズルは、六角形のボード上の塗りつぶしです。ここでプロトタイプを試すことができます。

_{(出典: hacker.org )}

パズルの仕組みは次のとおりです。上から色を選択すると、左上のタイルから塗りつぶしが始まります。これにより、ボードが徐々に単色に変換されます。課題は、特定の数の手でこれを行うことです。

これに似たパズルをいくつか作成しましたが、キーは、作成方法を知らずに解決するのが難しいボードを生成するアルゴリズムを使用することです. たとえば、ここでは塗りつぶしを逆にしてボードを作成する場合があります。塗りつぶしがなくなるまで、ソリッド ボードから逆方向に作業します。これにかかったステップ数がわかっているので、これを解の下限として設定できます。

私が直面している問題は、このアプローチを試みると、上限が高すぎることです。ランダムに移動しても、この手数以内にパズルを解くのは簡単です。

解決策ではないアプローチは、ランダムなボードを生成し、それを最適に解決して、これをターゲットに設定することです。ポイントは、最適に解くことが NP 時間または少なくともハード P であるパズルを作成することです。

だから私が探しているのは、非常に難しいボードを生成できるアルゴリズムであり、それらを解決することは、ボードが大きくなるにつれて深刻な課題になります.

Answer 1

私は長方形の洪水パズルをたくさんプレイしました（http://labpixies.com/gadget_page.php?id=10）。Hexバージョンを見て興奮しています！難しいゲームを見つけるのは簡単だと思います。同じ色の大きなブロックがパズルに表示されないようにします。少なくとも私が見た長方形のケースでは、少数のステップで解くことができるほとんどすべてのパズルは大きなカラーブロックを持っています。

PSあなたの「下限」は無効だと思います。前進するとき、良い戦略が使用されれば、実際にはより少ないステップで終了することができます。「下限」は、実際には最適なソリューションの上限です。

Answer 2

困難な構成の感触をつかむために、NP完全またはPであることを証明しようとします。

また、六角形を抽象化し、表現をグラフとして使用します。

Answer 3

RSA 暗号化を行う場合、素数を見つけるのではなく、乱数を選択してテストを適用すると、その数が素数である確率がますます高くなりますが、それを証明することはありません。

私は同じことを提案します。パズルが望ましい特性を持っている可能性が高い条件を見つけて、それらをテストしてみてください。または、遺伝的アルゴリズム/ニューラル ネットワークを使用して、「良い」パズルを認識するようにトレーニングすることもできますが、これは同じことです。