如何使用递归回溯 (Java) 找到特定迷宫的解决方案?
How do I find the solution of a particular maze using recursive bactracking (Java)?
我正在尝试编写一个递归解决迷宫的程序。完成一个步骤后,将一个 'x' 字符放置在迷宫中的该位置并打印迷宫,如果迷宫到达死胡同,它会通过从中删除 'x' 来回溯其最后的递归步骤那个位置。
当运行时,程序总是停在第一步;它并没有完全解决迷宫
我试过:
-硬编码每个连续的步骤以避免迷宫中的墙(但这违背了使用递归的目的)
-开始第一步随机取(但这会导致ArrayIndexOutOfBoundsException)
import java.util.Random;
public class MazeTraversalWithRecursiveBacktracking
{
private static Random random = new Random();
public static void main(String args[])
{
char [][] maze = {{'#', '#', '#', '#', '#', '#','#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.','.', '.', '.', '.', '.', '#'},
{'.', '.', '#', '.', '#', '.','#', '#', '#', '#', '.', '#'},
{'#', '#', '#', '.', '#', '.','.', '.', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '#','#', '#', '.', '#', '.', '.'},
{'#', '#', '#', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.','.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#','.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.','.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#','#', '#', '#', '#', '#', '#'}};
printMaze(maze);
mazeTraversal(maze, 2, 0);
}
public static void mazeTraversal(char [][] maze, int currX, int currY)
{
int choice = -1;
try
{
maze[currX][currY] = 'x';
printMaze(maze);
boolean chosen = false;
if ((currX == 4) && (currY == 11)) //end of the maze
{
System.out.println("Maze completed");
return;
}
while(!chosen)
{
choice = 1;
//System.out.println("Choice "+choice);
if (choice == 0)
{
if (maze[currX-1][currY] == '.')//up
{
System.out.println("Chose up");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 1)
{
if (maze[currX][currY+1] == '.')//right
{
System.out.println("Chose right");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 2)
{
if (maze[currX+1][currY] == '.')//down
{
System.out.println("Chose down");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 3)
{
if (maze[currX][currY-1] == '.')//left
{
System.out.println("Chose left");
chosen = true;
}
else
choice = random.nextInt(4);
}
else
{
System.out.println("Haven't chosen");
choice = random.nextInt(4);
}
//System.out.println(choice+" "+chosen);
}
System.out.println(choice+" "+chosen);
if (choice == 0)
mazeTraversal(maze,currX-1,currY);
else if (choice == 1)
mazeTraversal(maze,currX,currY+1);
else if (choice == 2)
mazeTraversal(maze,currX+1,currY);
else if (choice == 3)
mazeTraversal(maze,currX,currY-1);
else //backup
{
recursiveBacktrack(maze, currX, currY);
}
}
catch(ArrayIndexOutOfBoundsException ex)
{
ex.printStackTrace();
System.out.println("Maze finished with choice = "+choice);
}
}
public static void recursiveBacktrack(char [][]maze, int currX, int currY)
{
maze[currX][currY] = ' ';
}
public static void printMaze(char maze[][])
{
for(int i = 0; i < 12; ++i)
{
for(int j = 0; j < 12; ++j)
{
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
System.out.println();
System.out.println();
}
}
预期结果:预期结果是递归解决迷宫的预期结果,通过在每个递归步骤后重新打印整个迷宫来显示每次尝试。 '#'是一堵墙,'.'是一个空闲的space,'x'是一个spaced,已经被占用了。
实际结果:如前所述,我得到的实际结果只是第一个递归步骤,之后程序无限循环。
错误信息:偶尔,我收到错误信息 ArrayIndexOutOfBoundsException: -1
让我们先看看 isValidDirection
和 isSolution
应该如何工作:
public boolean isValidDirection(x, y) {
return ((x < maze.length) &&
(x >= 0) &&
(y < maze[x].length) &&
(y >= 0) &&
(maxe[x][y] == '.'));
}
public boolean isSolution(x, y) {
return isValidDirection(x, y) && (((x % maze.length) - 1 == 0) || ((y % maze[x].length) - 1 == 0));
}
让我们来实现迷宫赛跑者:
public boolean mazeRunner(x, y) {
if (!isValidDirection) {
//TODO: output the attempt
}
maze[x][y] = 'x';
//add (x,y) to current attempt
//we need to count attempt length
if (isSolution(x, y)) {
//TODO: output the successful attempt
} else if ((
(mazeRunner(x - 1, y)) ||
(mazeRunner(x + 1, y)) ||
(mazeRunner(x, y - 1)) ||
(mazeRunner(x, y + 1))
) == false) {
//TODO: Output the current failed attempt
}
maze[x][y] = '.';
//TODO: remove (x, y) from the current attempt
}
public void startMazeRunning(char[][] maze, x, y) {
this.maze = maze;
}
当然,您需要确保定义并正确初始化了所有需要的成员。
我正在尝试编写一个递归解决迷宫的程序。完成一个步骤后,将一个 'x' 字符放置在迷宫中的该位置并打印迷宫,如果迷宫到达死胡同,它会通过从中删除 'x' 来回溯其最后的递归步骤那个位置。
当运行时,程序总是停在第一步;它并没有完全解决迷宫
我试过:
-硬编码每个连续的步骤以避免迷宫中的墙(但这违背了使用递归的目的)
-开始第一步随机取(但这会导致ArrayIndexOutOfBoundsException)
import java.util.Random;
public class MazeTraversalWithRecursiveBacktracking
{
private static Random random = new Random();
public static void main(String args[])
{
char [][] maze = {{'#', '#', '#', '#', '#', '#','#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.','.', '.', '.', '.', '.', '#'},
{'.', '.', '#', '.', '#', '.','#', '#', '#', '#', '.', '#'},
{'#', '#', '#', '.', '#', '.','.', '.', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '#','#', '#', '.', '#', '.', '.'},
{'#', '#', '#', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#','.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.','.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#','.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.','.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#','#', '#', '#', '#', '#', '#'}};
printMaze(maze);
mazeTraversal(maze, 2, 0);
}
public static void mazeTraversal(char [][] maze, int currX, int currY)
{
int choice = -1;
try
{
maze[currX][currY] = 'x';
printMaze(maze);
boolean chosen = false;
if ((currX == 4) && (currY == 11)) //end of the maze
{
System.out.println("Maze completed");
return;
}
while(!chosen)
{
choice = 1;
//System.out.println("Choice "+choice);
if (choice == 0)
{
if (maze[currX-1][currY] == '.')//up
{
System.out.println("Chose up");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 1)
{
if (maze[currX][currY+1] == '.')//right
{
System.out.println("Chose right");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 2)
{
if (maze[currX+1][currY] == '.')//down
{
System.out.println("Chose down");
chosen = true;
}
else
choice = random.nextInt(4);
}
else if (choice == 3)
{
if (maze[currX][currY-1] == '.')//left
{
System.out.println("Chose left");
chosen = true;
}
else
choice = random.nextInt(4);
}
else
{
System.out.println("Haven't chosen");
choice = random.nextInt(4);
}
//System.out.println(choice+" "+chosen);
}
System.out.println(choice+" "+chosen);
if (choice == 0)
mazeTraversal(maze,currX-1,currY);
else if (choice == 1)
mazeTraversal(maze,currX,currY+1);
else if (choice == 2)
mazeTraversal(maze,currX+1,currY);
else if (choice == 3)
mazeTraversal(maze,currX,currY-1);
else //backup
{
recursiveBacktrack(maze, currX, currY);
}
}
catch(ArrayIndexOutOfBoundsException ex)
{
ex.printStackTrace();
System.out.println("Maze finished with choice = "+choice);
}
}
public static void recursiveBacktrack(char [][]maze, int currX, int currY)
{
maze[currX][currY] = ' ';
}
public static void printMaze(char maze[][])
{
for(int i = 0; i < 12; ++i)
{
for(int j = 0; j < 12; ++j)
{
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
System.out.println();
System.out.println();
}
}
预期结果:预期结果是递归解决迷宫的预期结果,通过在每个递归步骤后重新打印整个迷宫来显示每次尝试。 '#'是一堵墙,'.'是一个空闲的space,'x'是一个spaced,已经被占用了。
实际结果:如前所述,我得到的实际结果只是第一个递归步骤,之后程序无限循环。
错误信息:偶尔,我收到错误信息 ArrayIndexOutOfBoundsException: -1
让我们先看看 isValidDirection
和 isSolution
应该如何工作:
public boolean isValidDirection(x, y) {
return ((x < maze.length) &&
(x >= 0) &&
(y < maze[x].length) &&
(y >= 0) &&
(maxe[x][y] == '.'));
}
public boolean isSolution(x, y) {
return isValidDirection(x, y) && (((x % maze.length) - 1 == 0) || ((y % maze[x].length) - 1 == 0));
}
让我们来实现迷宫赛跑者:
public boolean mazeRunner(x, y) {
if (!isValidDirection) {
//TODO: output the attempt
}
maze[x][y] = 'x';
//add (x,y) to current attempt
//we need to count attempt length
if (isSolution(x, y)) {
//TODO: output the successful attempt
} else if ((
(mazeRunner(x - 1, y)) ||
(mazeRunner(x + 1, y)) ||
(mazeRunner(x, y - 1)) ||
(mazeRunner(x, y + 1))
) == false) {
//TODO: Output the current failed attempt
}
maze[x][y] = '.';
//TODO: remove (x, y) from the current attempt
}
public void startMazeRunning(char[][] maze, x, y) {
this.maze = maze;
}
当然,您需要确保定义并正确初始化了所有需要的成员。