問題タブ [sliding-tile-puzzle]

8 パズルの訪問済み状態が再び生成されないようにする方法を実装しようとしています。
私の最初のアプローチは、訪問した各パターンをリストに保存し、アルゴリズムが子を生成するたびに線形チェックを行うことでした。今、私はリストアクセスを通じて
これを間に合わせたいと思っています。O(1)8 パズルの各パターンは、1 から 9 までの数字の順列順列です (9 は空白のブロックです)。たとえば、125346987 は次のようになります。

1 2 5
3 4 6
_ 8 7

この種の可能な順列の総数は約 363,000 (9!) です。これらの数値をそのサイズのリストのインデックスにハッシュする最良の方法は何ですか?

次のルールでパズルを解く手順を見つけるプログラムを作成しようとしています。

• 4x4 グリッド内の任意の色のセットが与えられた場合、同じ数の色で終了パターンに一致するように試みます。
• 色は交換されませんが、水平または垂直に回転します。

{わ、わ、わ、わ}

に回転することができます

{W、W、W、B}

{B、W、W、W}

{わ、わ、わ、わ}

• パズル全体は 16 ステップ未満で解決できます。

パズル自体のデータを保存する方法はすでにわかっていますが、ステップを表示できるソリューションを見つけることについてどのように進めるかについて苦労しています。深さは 16 ステップに制限されているので、力ずくでやってみることは問題ありませんが、パターンを確立する方法がわかりません。

これは、ルービック キューブを解くのに似ています。私はすでに次のリソースを見てきました。

• stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726#34656726

• stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically

• amzi.com/articles/rubik.htm

• chessandpoker.com/rubiks-cube-solution.html

そして15の数の問題

• stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

この質問をできるだけ明確にするために、a) 手順を保存/印刷し、b) 手順を最小限に抑えるソリューションを見つけるには、どのような方法がよいでしょうか?

隣接セルの 2 つの番号が互いに連続しないように、次の図の 1 から 8 までの番号を付ける必要があります。

各 * には 1 から 8 までの数字が含まれており、隣接する * は連続した数字ではありません。

マンハッタン ヒューリスティックとマンハッタンおよび線形競合ヒューリスティックのみを使用して、15 パズルの A-star アルゴリズムをコーディングしました。

私の質問は、いくつかの特定のパズル インスタンスでは、線形競合により、a-Star を単独で使用するマンハッタン ヒューリスティックよりも多くのノードが作成および探索される可能性があるかどうかです。

50回未満の移動を必要とするプログラムで解決しようとしたパズルインスタンスのほとんどは、マンハッタンだけを使用して指定されたメモリで適切な時間で解決し、ヒューリスティックとして線形競合と組み合わせてより速く解決するため、50回以上の移動を必要とするインスタンスはプログラムを実行します無期限にマシンをハングアップさせますが、マンハッタンを使用して 42 回の移動が必要な特定の問題は、私のプログラムによって最大 8 秒で解決されますが、同じもので線形競合を使用すると、プログラムが無期限に実行され、マシンがハングアップします。

コードを何度も調べましたが、線形競合またはマンハッタン ヒューリスティック コードにエラーが見つかりません。したがって、この一般的な質問を確認してください。

次のインスタンスは、上記の問題を引き起こします。

A* 検索と幅優先検索を使用して、8 パズルで勝利のゲーム状態を見つけています。勝利状態はこんな感じ

このようなリストとして保存されます

ヒューリスティック関数を使用して各ノードに (その状態に基づいて) スコアを付けましたが、最高のスコアが付けられたノードに優先順位を付ける方法が、プログラムの速度を大幅に低下させていると思います。実際、私が作成した幅優先探索アルゴリズムは、A* アルゴリズムよりもはるかに優れています (ただし、内部の仕組みのほとんどは同じですが)。

A* 検索を遅くしている主な原因は、フリンジ (ノードを保持するリスト) 内の位置を使用して、優先順位を付ける次のノードを示していることだと思います。

ご覧のとおり、ノードがフリンジに追加されるたびに、スコアがそれよりも悪いノードを探し、その前に自分自身を挿入します。これにより、fringe.pop(0) を実行したときに、最高スコアのノードと少なくとも同点になることが保証されます。しかし、巨大なリストの真ん中にアイテムを挿入するのは、とても速いアクションではありませんか? より良い代替手段は何ですか？

また、フリンジ リストを並べ替えないことも検討しましたが、それも同様に悪いか悪いように思えます (ノードがポップ アウトされるたびにリスト全体を検索する必要があるためです。

私はphpを使って3x3のパズルソルバーを作っています。ゼロは移動できるフリースペースです。例えば：

に

に

私はすでに乱数発生器を作成しました - 50 のランダムな動きが行われます。しかし、私はソルバーアルゴリズムを使用しています。

出力は、それを解決するためのすべてのステップである必要があります。

ワンステップパズルを解くための作業方法はすでに取得していますが、それを再帰的に使用する方法がわかりません。

8 パズルでは、ボードに空白のタイル (0 で表される) が見つかった場合、1 回の移動で到達できる隣接するすべてのボードを取得する必要があります。

実装で 2 次元のボードを 1 次元の配列にマッピングしたのでindex()、コードで使用することは理にかなっています。

nowを実装するためのエレガントな方法を理解できないneighbors()ため、かなりの冗長コードが含まれるようになりました。