3x3グリッドパズル解決（JS）

Question

私は3x3グリッドに分割された画像を持っています。グリッドは配列で表されます。各列または行を回転させることができます。 、それは常に解けるだろう

[5,3,9] 
[7,1,4] 
[8,6,2] 

：

[1,2,3] 
[4,5,6] 
[7,8,9] 

など何かから開始する：例えば、一番上の行[1,2,3]は[3,1,2]など

配列のように終わるために必要になる可能性これはチェックする必要はありません。

私は '1'を探して、正しい場所まで左に移動しています.2,3などでも終わりますが、終わりには円で終わります。

私に出発点/参照を与えることができたとしても、何か助けていただければ幸いです。私はこのことを通して考えることはできません。

Answer 1

あなたの問題は、ある値をシフトする動きが他のものを混乱させることです。私は十分な集合理論では正確な解を試すことができると思うが、ここではヒューリスティックが働く可能性がより高い。

最初に、ある行のすべての数値がその行に属している場合は、解くのは簡単ではないか、一部の値が入れ替わっていることに注意してください。 [2,3,1]は簡単ですが、[3,2,1]はスワップされます。

したがって、1つ左上に配置するよりも「簡単な」ターゲットは、すべての行をその状態にすることです。どうしたらいい？列を見てみましょう...

列に各行の番号が1つ含まれている場合は、上と同じ状態になります（数字が正しい行にあるか、スワップされているかのように単純です）。

ので、私は何を示唆していることである。

for column in columns: 
     if column is not one value from each row: 
      pick a value from column that is from a duplicate row 
      rotate that row 
    for column in columns: 
     as well as possible, shift until each value is in correct row 
    for row in rows: 
     as well as possible, shift until each value is in correct column 

は今、それはそれは近づく傾向がありますが、動作することが保証されておらず、「ほとんど右」配置のいくつかのセットを解決することができます。

だから、私はループ内に置いて、実行ごとに状態の「ハッシュ」を記録します（たとえば、行ごとに読み込まれた値を含む文字列）。状態が既に発生しているので（私たちは自分自身を繰り返しているので）私が検出した場合（ハッシュがすでに見ていたものかどうかをチェックすることによって）、呼び出しを行うたびに、混合する「ランダムシャッフル」が呼び出されます。

だから、私たちが一度閉じてしまえば、私たちは仕事の機会があり、それがループに詰まったときに私たちが頼りにするシャッフルがあるという考えです。

私は言ったように、私はこれを行うよりスマートな方法があると確信していますが、私は絶望的だったし、Googleで何かを見つけることができなかった場合、それは私が試みるヒューリスティックのようなものです...私も確認していない以上、右であるが、より一般的な戦術は、次のとおりです。

• （パズルが「線形」である場合には、知る意味で）
• 試して非常に近いソリューションを解決する何かを識別それは

を繰り返し、それは私がここで言っている本当にすべてだ場合に

シャッフルを繰り返します。

Answer 2

グリッドは3x3なので、解を見つけることができないだけでなく、の移動数が最小でであることがわかります。

この目的でBreadth First Searchを使用する必要があります。

各構成を9要素の線形配列として表します。移動ごとに、別の構成になります。配列は本質的に1-9の間の数の置換であるので、9だけ存在するだろう！ = 362,880の異なる構成が可能です。

各構成をノードと見なし、各移動をエッジとみなすと、O（n）のグラフ全体を探索できます（nは構成の数です）。これまでに見た設定を再解決しないことを確認する必要があるので、にという配列が必要です。各設定は、表示された通りにマークされます。

「解決済み」設定に到達すると、元の設定を保存する「親」アレイを使用して実行された移動をトレースバックすることができます。

また、4x4グリッドの場合、nは（4x4）と等しいので、問題はかなり難しいでしょう。 = 16！ = 2.09227899×10^13である。しかし、このような小さな問題では、ソリューションをかなり早く見つけることができます。

編集：

TL; DR：

• かなり速いことで動作が保証され、。 362,880は今日のコンピュータのかなり小さい番号です
• これは、移動の最短シーケンスを見つけるでしょう。