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:
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 :)
Edit: Modified Code
public static void main(String[] args) {
int row = 0, col = 0;
char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr, row, col);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr, row, col);
} else {
System.out.println("No Solution");
}
}
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
//displays maze without dead end indicators
if(mazeArr[row][col] == '~') {
//mazeArr[row][col] = ' ';
}
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
}
}
//indicates starting point for the maze to start solving and recursively calls algorithm method that is overloaded
//pre: char 2D array mazeArr
//post: returns a boolean value from the overloaded algorithm method
public static boolean algorithm(char[][] mazeArr) {
int row = 1, col = 1; // where maze starts
return algorithm(mazeArr, row, col);
}
//solves the maze looking for a solution (if there is one), modifies the 2D array accordingly
//to the algorithm to trace the solution
//pre: char 2D array mazeArr, int row and col
//post: returns boolean value depending on the algorithms solution
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // found the target/exit
return true; //maze is completely solved
}
if (mazeArr[row][col] == ' ') { // if there is a path
mazeArr[row][col] = '@'; //mark as visited, block off path to not go back here again
}
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] = '~'; // indicates that this index is a dead end
}
return false;
}
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 if statements that check a certain direction (north, ...etc), will execute a return in 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:
for loopsrow and col variables in your main program: these should have no business there.#) 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;
}
}
From comments I understood you don't want to use loops. In that case, use recursion for finding the starting cell in a separate, recursive function, and return the found spot as a single integer (row*width + col).
Here is the corresponding code:
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) {
displayMaze(mazeArr, 0, 0); // add the arguments
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row >= mazeArr.length) {
return; // all done
}
if (col >= mazeArr[0].length) {
System.out.println();
displayMaze(mazeArr, row + 1, 0);
} else {
System.out.print(mazeArr[row][col] + " ");
displayMaze(mazeArr, row, col + 1);
}
}
public static int findStart(char[][] mazeArr, int i) {
// Look for starting point. i is combination of row/col
int row = i / mazeArr.length;
if (row >= mazeArr.length) {
return -1; // all done, and not found
}
int col = i % mazeArr[0].length;
if (mazeArr[row][col] == '#') {
return i; // found it
}
return findStart(mazeArr, i + 1);
}
public static boolean algorithm(char[][] mazeArr) {
int i = findStart(mazeArr, 0);
if (i == -1) {
return false; // No starting point found
}
int row = i / mazeArr.length;
int col = i % mazeArr[0].length;
return algorithm(mazeArr, row, col);
}
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;
}
}