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 的构造函数创建一个大小为 nc +2 x nr +2 的网格，用 16 填充所有边框单元格和所有内部单元格15。然后它以网格中间单元格的坐标开始递归调用 Create()。

Create() 首先调用 int[] perm = randPerm( 4 );，它创建一个长度为 4 的数组，其中包含整数 0 - 3，并对其进行简单的随机洗牌。 perm[] 的内容用于 select 来自 DX[] 和 DY[] 的一对值。

此方法使用 ^ 运算符，它是一个 XOR 或 Exclusive Or 函数来修改调用该方法的单元格及其相邻单元格的值如果单元格的内容为 15，则按照 perm[]、DX[] 和 DY[] 的内容指定的随机顺序。通过只检查 15，以前修改过的单元格不会改变，边框周围的墙保持不变。另外，中间单元格的none可以用这个方法改成16。

每个包含值 15 的单元格都是 XOR'd，其值来自 TWO[]，也是随机 select，不包括 16，因为 p由perm的内容推导出来，约束在0 - 3之间。通过这样做，每个包含 15 的单元格都会更改为不同的数字 - 但这些数字可以提前知道，因为中间单元格的可能值受到 [=40= 所有可能结果的限制].

由于 Random 对象 r 是用 seed 变量初始化的，我相信每次初始化 JVM 时使用相同的 seed 都会产生相同的迷宫。因此，通过更改 seed 的值，您将生成一个不同于 seed 的每个其他值的不同迷宫。不过，在这一点上我可能是错的，而且无论 seed 的值如何，每次都可能不同。我不熟悉 Random.

的内部工作原理

至于你如何知道迷宫是否真的可以解决每个实例，我不能在不知道迷宫中每个可能的值代表什么的情况下说。我想有些数字被认为是不可逾越的，而另一些则不是？

考虑到所呈现的内容，我认为无法保证每个迷宫都有有效的解决方案，因为此实施实际上只是创建一组随机的图块，并且肯定会有一些情况不是解决方案。但是，您并没有规定每个迷宫都必须是可解的；只是独一无二的。如果您想每次都保证一条可解决的路径，则必须在此处插入一些额外的逻辑才能实现。

Java - 用唯一解创建一个迷宫

Java - create a maze with a unique solution

maze

path