algorithm - この種のゲームを解決する最良の方法はどれですか?

Question

今夜、私は木のパズルを解こうとしたので、この種の問題をプログラムで解決する最良の方法はどれだろうと考えました。

目的は、立体のセット (3 次元のテトリスのピースなど) を組み合わせて、ピースが動きの種類に適合する場合にのみ構造に取り付けたりスライドさせたりできるという事実を考慮して、実行可能な方法で形状を形成することです。 (回転は無視し、90°回転のみ)。

私が何を意味するかを理解するために、この写真をチェックしてください。

Answer 1

私の最新の CS クラスでは、状態を C++ のオブジェクトとして表現することで機能する、一般的なパズル ソルバーを作成しました。各オブジェクトには、それが表す状態を別の状態と比較するメソッドがありました。これは、状態がすでに見られているかどうかを判断するためのメモ化に使用されました。各状態には、その状態から直接到達可能な状態を生成するメソッドもありました (つまり、ブロックの回転、ブロックの配置、ブロックの移動)。ソルバーは、状態のキューを維持し、キューの先頭から状態をポップし、それが目的の状態 (つまり、パズルの解決) であるかどうかを確認することで機能しました。そうでない場合は、メモ化 (ハッシュ化されたセットを使用) をチェックして、状態が既に表示されているかどうかを確認しました。そうでない場合は、現在の状態から到達可能な状態が生成され、キューの末尾に追加されました。空のキューは、解けないパズルであることを示しています。

そのようなものを 3D で概念化するのは難しいでしょうが、それがコンピューター化されたパズル解決の基本的なアプローチです。

Answer 2

3 次元polyominoパッキング問題のより簡単なサブセットのようです。その主題に関するさまざまな学術論文があります。

Answer 3

処理したいパズルがリンクした写真のパズルである場合、可能性のある解決策のツリーを検索して、一番下にたどり着くことができるでしょう。

各パズルのピースが面に取り付けられた多数の立方体であり、各ピースを構成する立方体として各エッジに 4 回、より大きな立方体に合わせてパズルを解く場合、次のように進めます。

各ピースの任意の立方体をその原点として宣言します。各パズル ピースには 24 回の回転が可能であることに注意してください。元の立方体の考えられる面ごとに 1 つの向きが上向きになり、その位置での垂直軸を中心に 4 回の回転が可能になります。

同じ最終ピースを生成する可能性のある方向を探すことによって、検索空間を選別しようとします。特定の回転に続いて、元のキューブをピースの他のキューブのいずれかに変換すると、以前とまったく同じ占有ボリュームが得られます。ローテーションを考慮し、将来の検討からそのローテーションを選別します。

袋から一枚取り出します。バッグにピースがない場合、これが解決策です。ソリューション ボリュームの各セル、および各セルの引っ張られた部分の各回転をループします。ピースが完全に検索ボリューム内にあり、他のピースと重ならない場合は、この段落に再帰します。それ以外の場合は、次のローテーションに進みます。ローテーションがこれ以上ない場合は次のセルに進みます。それ以上セルがない場合は、解決せずに戻ります。

最後の段落が解決せずに戻ってきた場合、パズルは解決できませんでした。

Answer 4

コンピューターでは可能な組み合わせの数が少ないため、これは多かれ少なかれ小さな問題なので、単純な検索アルゴリズムを試してみます。つまり、考えられるすべての構成をチェックし、この構成の結果から最終的な構成 (この場合はキューブ) になるまで続くアルゴリズムを意味します。

問題は、すべての状態チェックと、ある状態から別の状態への変換を実行できるプログラムを作成することです。構成が物理的に可能かどうかを確認する必要があるためです。