Java - ユニークなソリューションで迷路を作成

Question

私は現在、迷路を通して単一の解決策を見つけるJavaプログラムを作成しようとしています。私はいつもどのように上記の方法を把握しようとしている迷路を解決するための方法を作り始める前に、そう

private void Create (int x, int y, int val) { 
     int[] perm = randPerm(4); 
     m[x][y] ^= val; 
     for (int i=0; i<4; ++i) { 
      int p = perm[i]; 
      if (m[x+DX[p]][y+DY[p]] == 15) { 
       m[x][y] ^= TWO[p]; 
       Create(x+DX[p], y+DY[p], TWO[p^2]); 
      } 
     } 
    } 

：これを行うには、私はユニークなソリューションを持っている迷路を作成し、作成する方法を使用していますユニークなパスを持つ迷路を作成します（p^2のように が使用されています）。では、上記の方法はどのように機能しますか？

private int[][] m; // maze representation 
    private int rows; // number of rows in the maze 
    private int cols; // number of columns in the maze 
    private final static byte[] TWO = { 1, 2, 4, 8, 16}; 
    private final static byte[] DX = { 0,+1, 0,-1}; 
    private final static byte[] DY = {-1, 0,+1, 0}; 
    private boolean done; // used in finding a single solution. 
    private long count; // used in finding the number of solutions. 
    private Random r;  // for generating random integers. 

public Maze (int nr, int nc, int seed) { 
     r = new Random(seed); 
     rows = nr; cols = nc; 
     m = new int[nr+2][nc+2]; 
     for (int r=1; r<=nr; ++r) 
     for (int c=1; c<=nc; ++c) 
      m[r][c] = 15; 
     for (int r=0; r<nr+2; ++r) 
      m[r][0] = m[r][nc+1] = 16; 
     for (int c=0; c<nc+2; ++c) 
     m[0][c] = m[nr+1][c] = 16; 
     Create(nr/2+1, nc/2+1, 0); 
    } 

private int[] randPerm(int n) { 
     int[] perm = new int[n]; 
     for (int k=0; k<n; ++k) perm[k] = k; 
     for (int k=n; k>0; --k) { 
     int rand = r.nextInt(k); 
     int t = perm[rand]; perm[rand] = perm[k-1]; perm[k-1] = t; 
     } 
     return(perm); 
    } 

Answer 1

これはもう少し時間がかかりましたが、ここに私が持っているものがあります。

まず、Mazeのコンストラクタは、サイズX nr +2nc +2のグリッドを作成し、16と15を有する内側セルの全てとの境界セルの全てを満たします。次に、グリッドの中央にあるセルの座標で始まるCreate()を再帰的に呼び出します。 int型0 - 3を含む長さ4の配列を作成し、その上に、単純なランダムシャッフルを行うint[] perm = randPerm(4);を呼び出すことによって

Create()開始。 perm[]の内容は、DX[]とDY[]の値の組を選択するために使用されます。

この方法は、perm[]の内容によって決定されるように、ランダムな順序でメソッドが呼び出されたセルの値、及びその隣接セルを変更するXOR又はExclusive Or関数である^演算子を使用DX[]とDY[]セルの内容が15の場合15をチェックするだけで、以前に変更されたセルは変更されず、境界線の周りの壁は変更されません。さらに、この方法で中間セルを16に変更することはできません。

値15を含むすべてのセルがTWO[]の値、また0 - 3間に拘束されているpermの内容に由来する16pため除く、ランダムに選択されたとXOR'dあります。これにより、15を含むすべてのセルが異なる番号に変更されます。中間セルの可能な値は、可能なすべての結果である15^TWO[p]によって制限されるため、これらの数値は事前に知ることができます。

Randomオブジェクトrがseed変数で初期化されているので、私は同じseedを使用して同じ迷路をJVMが初期化されるたびに生成すると考えています。したがって、seedの値を変更すると、他の値であるseedとは異なる別の迷路が生成されます。私はこの時点で間違っている可能性があります。seedの値に関係なく、毎回違うかもしれません。私はRandomの内部の仕組みに精通していません。

迷路が実際に解決できるかどうかをどのように知ることができるかについては、それぞれの可能な値が迷路内でどのようなものであるかを知らずには言えませんでした。私はいくつかの数字は、通過不可能と考えられていると思いますが、他の数字はそうではありませんか？

そして、提示されているものを考えると、私は1つが、この実装は本当にただのタイルのランダムなセットを作成しているので、有効な解決策を持っているそのすべての迷路を保証することができると思うし、いくつかになるはずがありませんがではない場合があります。しかし、あなたはそれぞれの迷路が解決できなければならないということを明記していませんでした。ちょうどユニークです。毎回解決可能なパスを保証したい場合は、それを実現するためにここにいくつかの追加ロジックを挿入する必要があります。