所以我目前正在尝试制作一个通过迷宫找到单一解决方案的 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 );
}
花了一点时间，但这就是我得到的。
首先，Maze的构造函数创建一个大小为 nc +2 x nr +2 的网格，用 16 填充所有边框单元格，用 15 填充所有内部单元格。然后，它从网格中间单元格的坐标开始递归调用Create()。
Create()首先调用int[] perm = randPerm( 4 );，它创建一个包含整数0 - 3的长度4数组，并对其进行简单的随机洗牌。perm[]的内容用于从DX[]和DY[]中选择一对值。
此方法使用 ^ 运算符，该运算符是一个XOR或Exclusive Or函数，用于根据 perm[] 、DX[] 和 DY[] 的内容以随机顺序修改调用该方法的单元格及其相邻单元格的值，如果单元格的内容15。通过只检查15，先前修改的单元格不会被改变，边界周围的墙壁保持不变。此外，使用此方法无法将任何中间单元格更改为16。
每个包含值15的单元格都XOR'd来自TWO[]的值，也是随机选择的，不包括16，因为p是从perm的内容派生的，这些内容在0 - 3之间受到限制。通过这样做，包含15的每个单元格都更改为不同的数字 - 但这些数字可以提前知道，因为中间单元格的可能值受到15 ^ TWO[p]所有可能结果的限制。
由于Random对象r是用seed变量初始化的，我相信每次初始化JVM时使用相同的seed都会产生相同的迷宫。因此，通过更改seed的值，您将产生一个不同的迷宫，该迷宫与seed的其他所有值都不同。不过，我在这一点上可能是错的，无论seed的价值如何，每次都可能不同。我不熟悉Random的内部运作。
至于你怎么知道迷宫是否真的可以解决每个实例，我不能说不知道迷宫中每个可能的值代表什么。我想有些数字被认为是无法通过的，而另一些则不是？
鉴于所呈现的内容，我认为不能保证每个迷宫都有一个有效的解决方案，因为这种实现实际上只是创建一组随机的图块，并且肯定在某些情况下没有解决方案。但是，你没有规定每个迷宫都必须是可解决的;只是独一无二的。如果你想保证每次都有一个可解决的路径，就必须在这里插入一些额外的逻辑来实现这一点。