問題タブ [sliding-tile-puzzle]

最終的には、テーブルを使用してスライダー パズルを作成していますが、現時点では新しいパズルを生成してタイルをシャッフルしていますが、コード内の何かがこれを正しく機能させていないようです。(すべての表のセルに値が入力されているわけではありません。など) 何が原因でしょうか?

私が書いているプログラムでは、body onload を使用してパズルを作成していますが、何らかの理由で Fiddle では機能しません:

フィドルの例

8 パズル ゲームを解く試みに幅優先探索アルゴリズムを実装しようとしました。しかし、場合によってはメモリ不足になりましたが、より単純なケースでは問題なく解決しました。

アルゴリズムを改善して修正するにはどうすればよいですか?

main.c

game.c

8 パズルを解くための独自のプログラムを Python で開発しました。最初は、「ブラインド」または情報に基づいていない検索 (基本的に総当たり) を使用して、すべての可能な後継者を生成および探索し、幅優先検索を使用しました。「目標」状態を見つけると、基本的に初期状態に戻り、それを解決するための最も最適化された手順を提供します (私が信じていること)。もちろん、検索に時間がかかり、目標を見つけるまでに 100,000 を超える状態が生成される初期状態もありました。

次に、ヒューリスティック - マンハッタン距離を追加しました。解決策は指数関数的に急速に現れ始め、調査された状態ははるかに少なくなりました。しかし、私の混乱は、生成された最適化されたシーケンスが、盲目的または情報に基づいていない検索を使用して到達したシーケンスよりも長い場合があることです。

私がやっていることは基本的にこれです：

1. 状態ごとに、可能なすべての動き (上、下、左、右) を探し、後続の状態を生成します。
2. 状態が繰り返しかどうかを確認します。はいの場合は、無視してください。
3. 州のマンハッタンを計算します。
4. マンハッタンが最も低い後継者を選び出し、リストの最後に追加します。
5. 目標状態かどうかを確認します。もしそうなら、ループを壊してください。

これが貪欲優先または A* と見なされるかどうかはわかりません。

私の質問は、これはマンハッタン距離ヒューリスティックに固有の欠陥であり、最適なソリューションが得られない場合があるのか​​、それとも何か間違っているのかということです。

以下はコードです。非常にきれいなコードではないことをお詫びしますが、ほとんどがシーケンシャルであるため、理解しやすいはずです。また、コードが長くなってしまったことをお詫び申し上げます。コードを最適化する必要があることは承知しています。また、コードをクリーンアップするための提案/ガイダンスをいただければ幸いです。それが何であるかは次のとおりです。

初期状態の一部と、確認したい場合に計算された最適化されたステップを次に示します (上記のコードでは、ブラインド検索とインフォームド検索のどちらかを選択するオプションが提供されます)

初期状態
- 283164507 ブラインド: 19 マンハッタン: 21
- 243780615 ブラインド: 15 マンハッタン: 21
- 102468735 ブラインド: 11 マンハッタン: 17
- 481520763 ブラインド: 13 マンハッタン: 23
- 723156480 ブラインド: 16 マンハッタン: 20

結果がすぐに得られる例 (数秒または数分以内) を意図的に選択しました。

皆様のご支援とご指導を賜りますようお願い申し上げます。

編集: いくつかの簡単な変更を行い、30 行以上を削減することができました。残念ながら、現時点では多くのことを行うことはできません。
注: 初期状態と、ブラインド vs インフォームド チョイスをハードコーディングしました。初期状態は変数「string」、Informed/Blindは変数「inf」[I/B]の値を変更してください。ありがとう！

私はこれにかなり慣れていないので、次のように呼び出します [element1,element2,element3]

上記のような配列があり、この配列の解決策を見つけたいと考えています。次の条件を満たす必要があります。

最初の要素 0:

から少なくとも 1 つのソリューションが必要です。[0,1,11],[0,2,11],[0,3,10],[0,4,10],[0,5,9],[0,6,9]

最初の要素 1:

これ ：[1,7,9],[1,5,11],[1,6,11]

最初の要素 2:

この ：[2,7,11],[2,8,10]

2 番目の要素と 3 番目の要素がソリューションごとに一意になるように (1 番目の要素 = 0、2 番目の要素 = 1、3 番目の要素 = 2)

o/p は : [0,1,11]および[1,7,9]および[2,8,10]

間違った出力: [0,1,11], [1,6,11] ,[2,8,10] ここでは、1 番目と 2 番目のパラメーター 3 は同じです。

山登りでランダムな 8 パズルを解くアルゴリズムを書こうとしています。最初の選択、最良の選択、およびランダムな再起動を使用して作成しましたが、常に無限ループに陥ります。それを防ぐ方法はありますか? また、ランダムなパズルを生成するときに、アルゴリズムを使用して、生成されたすべてのパズルが解けるようにしました。したがって、可解性の問題はありません。これは、ほぼ 100% のパズルで 8 つのパズルを解決するランダム リスタート タイプの関数です。