カラータイルにマッチするパズルを解決するスクリプトのアドバイス

Question

私は解決策を見つけるためにスクリプトを考案しようとしています。私はそれが私が最もよく知っているので、Pythonを使用しています。

ここに要点があります、ゲームは5種類の色のタイルで構成された10 x 14のボードです。仕組みは、水平または垂直軸に接触している同じ色の2つ以上のタイルのグループを選択できます（対角線はカウントされません）。その後、そのグループは消え、上記のタイルはすべて落ちて行きます。列にタイルが完全に空の場合、右側のタイルの残りの列が左に移動してギャップを埋めます。あなたはボードをクリアし、タイルを残さないで勝つ。ゲームボードの

小さな例、実際のものは10×14

まずステップある - ゲームのルールを尊重するPythonスクリプトを書きます。かなり簡単。

私は数値にタイルの色をマッピングし、このようなマトリックスの作成：私は行列を解析し、同じ色のすべての連続したタイルを見つけて、現在はすべての可能な移動のためのオブジェクトを作成

test_game_board = [ 
    [2, 2, 2, 1, 1, 1, 5], 
    [2, 2, 2, 3, 3, 1, 5], 
    [3, 2, 4, 5, 3, 3, 5], 
    [3, 3, 4, 5, 5, 3, 5], 
    [1, 1, 1, 1, 1, 3, 5], 
    [1, 1, 5, 5, 1, 4, 4]] 

をボード上の。

次に、ゲームボードのコピーを更新し、必要に応じてタイルをシャッフルしていくために、一定の適格な移動（後でロジックを選択するコメントを参照）を与えられたコードブロックがあります。

タイルが移動したので、適格な移動のリストを更新するには、もう一度ボードを確認してください。

適格な移動が残っている場合は、新しい移動を選択してください。 適格な移動が見つからない場合は、ボードをチェックして、ゲームを失ったか勝ったかを確認します。 ゲームを失った場合は、最初からやり直して元のゲームボードのレイアウトに戻します。

上記のパフォーマンスは、30-40回の移動で実行され、約0.0350秒で1回の試合が完了したようです。

セカンドステップ - 私はいくつかのアプローチを試みた移動

のシーケンスをピッキング：

• はランダムに各ターンの動きを選ぶ：でも、時間のスクリプトを実行した後、それはhasn試行された数百万回の移動のうち、正確な移動シーケンスが繰り返されました。

• 各移動にいくつのタイルがあり、それより大きなタイルが選択されたかを選択して重み付けを試みました。

• 可能な移動を順次実行します。ランダムオプションと同じですが、このようにして私は何らかの進歩を見せています。私は数日間余分なマシンでこれを実行しようとしましたが、それは1500万シーケンスを経て、未知数の可能な移動のそれほど遠くはありません。誰かが私はブルートフォース攻撃の私の現在のアプローチよりも、この他を解決するためのアルゴリズムを考案できる方法上の任意のリソースやアイデアを持っている場合

だから私は世界にそこに私の質問を推測です。私はpastebinにスクリプトを投稿することができますか何かが私のポストを既に膨らませたくありませんでした：P

Answer 1

私はこの仕事はNP-completeクラスに属していると思います。それを解決する簡単な方法ではありません。

あなたは何ができますか？ A* searchを試してみてください。ヒューリスティックでは、アクションによって削除できる要素をいくつか選んでみることができます（私はそれが正しい/最適であるとは確信していません。あなた自身でそれを学習しなければなりません）。

他のアプローチがあります（たとえば、constraint satisfaction）が、あなたのパズルのソルバーを実装するのは非常に難しいと思います。しかし、洞察のためにMinizincを見てください。私は「Kステップで現在のボードを空にすることは可能ですか？」という形でタスクを生成します。そうでない場合は、Kを増やしてMinizincを再度実行します。