I've been trying to make a program that could solve a maze recursively (should work for any maze). Majority of the recursion for the algorithm works but when the maze checks for dead ends and a way to reroute to find the solution (end point), the code doesn't work for it. I've tried multiple ways to debug but it hasn't gotten me far; I either get StackOverflowError or the algorithm works to backtrack by one position.
Note "char indicators" for the 2D array:
- '*' = walls
- '#' = start
- '$' = end
- ' ' = possible path/not a wall
- '@' = path
- '~' = dead end
Desired output:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ @ *
* * * * * * * ~ @ *
* ~ ~ ~ ~ ~ ~ ~ $ *
* * * * * * * * * *
Here is the code for the one that backtracks by only one position:
In this version I tried recursively calling after finding a position that could be backtracked and returning that position to retrace and find the solution
import java.util.*;
public class mazeOG {
public static void main(String[] args) {
allocateMaze();
}
public static void allocateMaze() {
char[][] mazeArr = {{'*','*','*','*','*','*','*','*','*','*'},//0
{'*','#','*','*','*','*','*','*','*','*'},//1
{'*',' ','*',' ',' ',' ',' ',' ','*','*'},//2
{'*',' ','*',' ',' ',' ','*',' ','*','*'},//3
{'*',' ',' ',' ','*',' ','*',' ','*','*'},//4
{'*','*','*',' ',' ',' ','*',' ','*','*'},//5
{'*','*',' ',' ','*',' ','*',' ','*','*'},//6
{'*','*',' ',' ','*',' ','*',' ',' ','*'},//7
{'*','*','*','*','*','*','*',' ',' ','*'},//8
{'*',' ',' ',' ',' ',' ',' ',' ','$','*'},//9
{'*','*','*','*','*','*','*','*','*','*'}};//10
//setting row and col to 0 for display method
int row = 0;
int col = 0;
System.out.println("Presolved maze:");
displayMaze(mazeArr, row, col); //displays presolved maze
row = 1;
col = 1;
boolean isSolved = false;
System.out.println("\nMaze solution:");
algorithm(mazeArr, row, col, isSolved); //create variable for solved maze, sends maze allocation to method that solves the maze
System.out.println();
row = 0;
col = 0;
displayMaze(mazeArr, row, col); //displays traced solved maze
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { //iterate through all (11) rows
if (col < mazeArr[row].length) { //iterate through all (11) columns
System.out.print(mazeArr[row][col] " "); //displays the current index in the array
displayMaze(mazeArr, row, col 1); //repeats this method by iterating through the columns first
return;
}
System.out.println(); //enters the line after each row for display purposes
displayMaze(mazeArr, row 1, col=0); //repeats this method by iterating through the rows
}
}
public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved){
boolean isPath = false; // assume there is no path
if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
return mazeArr;
} else { // IF MAZE IS NOT COMPLETELY SOLVED
// start searching thru the maze, assume there is no path
// THERE IS NO DEAD END
if (mazeArr[row - 1][col] == ' ') { // if north has a path
mazeArr[row - 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
}
if (mazeArr[row][col 1] == ' ') { // if east has a path
mazeArr[row][col 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col, isSolved); // repeat process going to next east spot
}
if (mazeArr[row 1][col] == ' ') { // if south has a path
mazeArr[row 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col, isSolved); // repeat process going to next south spot
}
if (mazeArr[row][col - 1] == ' ') { // if west has a path
mazeArr[row][col - 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
}
if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
isSolved = true; // maze has been solved
return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
}
// finds alternate path if there's a dead end
if (mazeArr[row][col] != '#') {
mazeArr[row][col] = '~'; //indicates that this index is a dead end
}
if (isPath == false) {
if (mazeArr[row - 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if north was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, --row, col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row - 1][col] == '@' && mazeArr[row][col 1] != '#') {// if east was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if south was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row][col-1] == '@' && mazeArr[row - 1][col] != '#') {// if west was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, --col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) { // if there's no way out, that means there is no solution
System.out.println("No Solution");
return mazeArr;
}
return mazeArr;
}
}
}
Output for this version:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
No Solution
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ * @ * *
* @ @ @ * * @ * *
* * * * @ * *
* * * * @ * *
* * * * @ @ *
* * * * * * * @ @ *
* ~ @ @ @ @ @ @ $ *
* * * * * * * * * *
Here is the code for the version that gets StackOverflowError:
In this version, I removed the section of the code that traces back by a position and recursively calls, instead, I just indicate that that position is a dead end and recursively calls the algorithm to search for the next position instead.
import java.util.*;
public class maze {
public static void main(String[] args) {
allocateMaze();
}
public static void allocateMaze() {
char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
// setting row and col to 0 for display method
int row = 0;
int col = 0;
System.out.println("Presolved maze:");
displayMaze(mazeArr, row, col); // displays presolved maze
row = 1;
col = 1;
boolean isSolved = false;
System.out.println("\nMaze solution:");
algorithm(mazeArr, row, col, isSolved); // create variable for solved maze, sends maze allocation to method that
// solves the maze
System.out.println();
row = 0;
col = 0;
displayMaze(mazeArr, row, col); // displays traced solved maze
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { // iterate through all (11) rows
if (col < mazeArr[row].length) { // iterate through all (11) columns
System.out.print(mazeArr[row][col] " "); // displays the current index in the array
displayMaze(mazeArr, row, col 1); // repeats this method by iterating through the columns first
return;
}
System.out.println(); // enters the line after each row for display purposes
displayMaze(mazeArr, row 1, col = 0); // repeats this method by iterating through the rows
}
}
public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved) {
boolean isPath = false; // assume there is no path
if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
return mazeArr;
} else { // IF MAZE IS NOT COMPLETELY SOLVED
// start searching thru the maze,
// assume there is no path
// THERE IS NO DEAD END
if (mazeArr[row - 1][col] == ' ') { // if north has a path
mazeArr[row - 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
}
if (mazeArr[row][col 1] == ' ') { // if east has a path
mazeArr[row][col 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col, isSolved); // repeat process going to next east spot
}
if (mazeArr[row 1][col] == ' ') { // if south has a path
mazeArr[row 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, col, isSolved); // repeat process going to next south spot
}
if (mazeArr[row][col - 1] == ' ') { // if west has a path
mazeArr[row][col - 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
}
if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
isSolved = true; // maze has been solved
return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
}
//code from here and below is for the case of a dead end
if (mazeArr[row][col] != '#' && isPath == false) {
mazeArr[row][col] = '~'; // indicates that this index is a dead end
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, col, isSolved);
}
if (isPath == false) { // if there's no way out, that means there is no solution
System.out.println("No Solution");
return mazeArr;
}
return mazeArr;
}
}
}
Any help would be really great! Thank you :)
CodePudding user response：
There are several issues, including:
A dead end should not trigger a new recursive call. Dead end marking should happen while backtracking from recursion, and should indicate to the caller that there was no success.
Each of the
ifstatements that check a certain direction (north, ...etc), will execute areturnin its block, meaning that if there is such a direction none of the other directions will be tried.As the recursive call does not return whether there was success or not, the caller has no way to know whether it should try in another direction
Not the problem, but:
- There is also quite some code repetition, which you should avoid.
- There is no good reason to make the display function recursive. Just iterate over the cells with two
forloops - Avoid
rowandcolvariables in your main program: these should have no business there. - As you mutate the maze, there should be no need to also return that maze. The caller will any how have access to the populated maze after the call.
- The code will be easier when you separate the search for the starting point (
#) from the rest of the algorithm.
One of the keys to a successful function is that returns a boolean, indicating whether the path was found or not. This way the algorithm can decide whether or not it should try again in another direction.
Here is the modification of your code:
import java.util.*;
public class Main {
public static void main(String[] args) {
char[][] mazeArr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr) {
for (char[] row : mazeArr) {
for (char cell : row) {
System.out.print(cell " ");
}
System.out.println();
}
}
public static boolean algorithm(char[][] mazeArr) {
// Look for starting point
for (int row = 0; row < mazeArr.length; row ) {
for (int col = 0; col < mazeArr[0].length; col ) {
if (mazeArr[row][col] == '#') {
return algorithm(mazeArr, row, col);
}
}
}
return false; // No starting point found
}
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // Found the target
return true;
}
if (mazeArr[row][col] == ' ') {
mazeArr[row][col] = '@'; // Mark as visited
} else if (mazeArr[row][col] != '#') { // Not allowed
return false;
}
// The core of the algorithm: try each direction until true is returned
if (algorithm(mazeArr, row, col - 1) // west
|| algorithm(mazeArr, row - 1, col) // north
|| algorithm(mazeArr, row, col 1) // east
|| algorithm(mazeArr, row 1, col) // south
) {
return true; // Path found
}
if (mazeArr[row][col] == '@') { // mark backtracking
mazeArr[row][col] = '~';
}
return false;
}
}