6 * 6パズルアルゴリズム

Question

私はランダムな順序で35個の数字（1〜35）を持つ6 * 6のパズルを持っています。ブランクのものを「レジスター」として使用し、数字を1つずつ移動させて順序を合わせます。私は3 * 3のパズルを扱うことができますが、6 * 6のものを扱う方法は？いくつかのヒントを教えてください。

Answer 1

考え方は同じですが、状態graphような問題を表し、shortest pathアルゴリズムを実行します。

アルゴリズムの効率が重要な場合は、admissible heuristic functionでかなり高速（代替品と比較して）になることが予想される通知アルゴリズム（A* algorithmなど）が必要な場合があります。
もっと簡単な解決策でも遅くても、BFSを実行することができます。

両方アルゴリズム（*、BFS）は、（最短経路を見つける）の両方完全（存在する場合は常に、solutuionを見つけ）と最適あります。

マクロを使用して、アルゴリズムの速度を上げるために、「良い」一連の動きを学習することもできます（）。作業速度の遅いソリューションを実装するまで、この改善は無視してください。

---

EDIT：コーディングガイドライン：グラフなどの問題で
ルック：このグラフとグラフは今G=(V,E)どこV = { all possible states}と

E = { (u,v) | can move from state u to state v within a single step }になりますが、 - あなたは（開始位置を持っていますソース、入力として与えられる）とターゲット（ソートされたパズル）を含む。 BFSまたはA *（添付されているウィキペディアのリンクでこれらの疑似コードを見てください）を開始して、ソースからデスティネーションまでのパスを見つけます。あなたはBFSから始めるべきです - それは簡単です。
最短経路アルゴリズムによって返されるパスは、開始ボードからターゲットに到達するために必要な一連の移動と同じです。

注：実際のグラフを作成する必要はありません。開始ノード（ソース）を保持し、その頂点を作成し、successors:V->2^V関数を持つ必要があり、各頂点の後継を与えます（正式にはsuccessors(v) = { (v,u) | (v,u) is in E }）。このようにして、グラフの関連部分をオンザフライで構築することができます。

Answer 2

このゲームの簡単な戦略は、一番上の行に正しい数字を置くことです（他の数字は気にしないため、最後の2つの数字は正しい場所に置くのが少し難しいので両方を同じ動きに配置しなければならない場合）、一番上の行をフリーズして左の列を続け、次に上の行と次に左の列を続けます。

最適な戦略ではありませんが動作し、コードするのは簡単です。

Answer 3

私は大学でこの同じ問題/パズルを学んだし、AIやヒューリスティックなテクニックやグラフ理論を含む非常に興味深い問題を勉強しました。 amitで述べたように、A *、BFS、ヒューリスティックをチェックすることを強く推奨します。

これは私の貢献です：これを解決しようとすると、を分割して戦略を征服することができます。この6x6グリッドは、お互いに接近した4つの3x3グリッドだけであると考えることができます。そして、それぞれを所定の順序で分離して解決しようとします。例えば

、次のアルゴリズム試すことができます。

1. は、左上のグリッドが1（つまり、作業スペースとして使用されます）を除いて、その作品のすべてが含まれていること方法であなたの作品をアレンジ。
2. 左上のグリッドを解決します。
3. ボトム右のもの（作業スペースとして使用されます）を除いて、そのすべての部分と干渉するように右上のグリッドを配置します。
4. 右上のグリッドを解決します。
5. ...など、独立してグリッドの数！言うべき最後の問題は、あなたが"あなたは右上のグリッドの右上隅には、作業スペースも任せることはできないとして、あなたは、スペース作業として残さつもりどのコーナーに注意を払う必要があるということです

未来の作品をそこに置くことは不可能なので、「欠けている作品」。

Ps1：作業スペースは、一時的にピースを逃して、ピースを操作するための空きスペースを持つことができる位置です。

Ps2：このコンテキストでは、グリッドはNxN個の部分の組み合わせであり、必ずしも順番に並べる必要はありません。

私は何らかの形で助けてくれることを願っています。 :-)

Answer 4

私たちが6 * 6の行列全体を横断すれば、私たちは一度に1つの小さな数しか見つけられず、それを適切な解ではない次の行列に移動します。この問題を解決するより良い方法は、与えられた行列のバイナリサーチを使うことです。バイナリ検索を適用すると、時間の複雑さが増します。この問題を解決するより良い方法は何ですか？

Answer 5

私は上記を解決しましたパズルの挿入アルゴリズムを使用しています。私はこのパズルを解くのに2日ほどかかった。ちょうどあなたが何かを尋ねなければならない場合は、以下の.NETコードを実行してください。私は上記の問題を解決するためにC＃inbuiltクラスを使用していません。これは純粋なコードです。コード付きロジックコードソリューション

private static void MazePuzzle() 
     { 
      /**** 
     * A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days. 
     * Problem is about Sorting a 2D Matrix with any number of row and column 
     * This problem is also known as Rat Maze puzzle 
     * It is also be a typical Backtracking Problem 
     * ***/ 
      const int _row = 6; 
      const int _coloumn = 6; 
      //int _column1 = _coloumn; 

      int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } }; 
      int [] _StoringArray1D=new int[_row*_coloumn]; 
      int i = 0; 
      int j = 0; 
      int _comparingArrayElement = 0; 
      int _swipeTemp = 0; 


      for (; i < _row; i++) 
      { 
       int _trackrow = 0; 
       for (;j <_coloumn; j++) 
       { 
        _trackrow = 0; 
        if(i==0 && j==0) 
        { 
          _comparingArrayElement= _doubleArray[i, j + 1]; 
         if(_comparingArrayElement<_doubleArray[i,j]) 
         { 
          _swipeTemp = _doubleArray[i,j+1]; 
          _doubleArray[i, j + 1] = _doubleArray[i, j]; 
          _doubleArray[i, j] = _swipeTemp; 

         }//innerMost if 
        }//For First time 
         else 
         { 
          int k = 0; 
          do 
          { 
           if (_trackrow == i || _trackrow < i) 
           { 
            for (; k < _coloumn; k++) 
            { 
             if(k==j && i==_trackrow) 
             { 
              break; 
             } 
             else 
             { 
             if(_doubleArray[_trackrow,k]>_doubleArray[i,j]) 
             { 
              int _swipetempPrevious=_doubleArray[_trackrow,k]; 
              _doubleArray[_trackrow,k]=_doubleArray[i,j]; 
              _doubleArray[i, j] = _swipetempPrevious; 
             } 
             else 
             { 
              //do nothing just traverse 
             }//swipe else 
             }//k==j else 
            }//inner for do while 
            _trackrow++; 
            k = 0; 
           }//trackrow if 
           else 
           { 
            break; 
           }//trackrow else 
          } while (true); 
         }//else 
       }//innner for 
       j = 0; 
      }//outer for 
      Console.WriteLine("End of Program"); 
     }//Maze Puzzle Method