0

I've been trying to create a maze solving algorithm in java. I've tried to do it with backtracking recursion.Here is my code:

public static boolean solver(String[][] maze, int i, int j){
    display(maze);//prints maze
    System.out.println();
    maze[i][j] = "*";
    if(maze[i][j+1] == "E" || maze[i][j-1] == "E" || maze[i+1][j] == "E" || maze[i-1][j] == "E")
        display(maze);
    else if(maze[i][j+1] != " " && maze[i][j-1] != " " && maze[i+1][j] != " " && maze[i-1][j] != " "){
        maze[i][j] = " ";
        return false;
    }
    if(maze[i][j+1] == " ")
        if(!solver(maze,i,j+1))
            maze[i][j] = " ";
    if(maze[i][j-1] == " ")
        if(!solver(maze,i,j-1))
            maze[i][j] = " ";
    if(maze[i+1][j] == " ")
        if(!solver(maze,i+1,j))
            maze[i][j] = " ";
    if(maze[i-1][j] == " ")
        if(!solver(maze,i-1,j))
            maze[i][j] = " ";
    return true;
}

and here is main method:

String[][] maze = {{"#","S","#","#","#","#","#","#","#","#","#","#","#"},
                   {"#"," "," "," "," "," ","#"," "," "," "," "," ","#"},
                   {"#"," ","#","#","#","#","#"," ","#","#","#"," ","#"},
                   {"#"," "," "," "," "," ","#"," ","#"," ","#"," ","#"},
                   {"#"," ","#","#","#"," ","#"," ","#"," ","#"," ","#"},
                   {"#"," "," "," ","#"," ","#"," "," "," ","#"," ","#"},
                   {"#"," "," "," ","#"," ","#"," "," "," ","#"," ","#"},
                   {"#"," ","#"," ","#"," "," "," "," "," "," "," ","#"},
                   {"#","#","#"," ","#","#","#","#","#","#","#","#","#"},
                   {"#"," "," "," ","#"," "," "," "," "," "," "," ","#"},
                   {"#"," ","#","#","#"," ","#","#","#","#","#"," ","#"},
                   {"#"," "," "," "," "," ","#"," "," "," "," "," ","#"},
                   {"#","#","#","#","#","#","#","#","#","#","#","E","#"}};
solver(maze,1,1);

This algorithm can solve a maze but there is a bug in this code and I couldn't solve the bug.

Output:

#S###########
#*****#     #
# ##### ### #
#     # # # #
# ### # # # #
#   # #   # #
#   # #   # #
# # #       #
### #########
#   #       #
# ### ##### #
#     #     #
###########E#

#S###########
#***  #     #
#*##### ### #
#     # # # #
# ### # # # #
#   # #   # #
#   # #   # #
# # #       #
### #########
#   #       #
# ### ##### #
#     #     #
###########E#

As you can see, it comes this way but while returning it doesn't remove stars correctly.

How can I solve this bug?

Oğuzhan Karahan
  • 13
  • 5
  • Please read: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – Turing85 Jan 11 '20 at 13:41
  • Does this answer your question? [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Turing85 Jan 11 '20 at 13:42

1 Answers1

0

Maybe it helps to abstract from the specific representation of the "maze" and consider a (perfect) maze as a spanning tree of an undirected graph on a 2-dimensional grid. Then you just have to implement any pathfinding algorithm you like on that grid. "Solving" a maze is just finding a path between two vertices on the border of the grid.

I have implemented lots of maze generation and pathfinding algorithms based on this graph-theoretic view, you can find my code and demo applications here:

https://github.com/armin-reichert/mazes

Armin Reichert
  • 21
  • 2
  • Welcome to StackOverflow, add some more description and code if it's required to understand the answer because it will resolve someone's else problem ASAP. – Nensi Kasundra May 12 '20 at 10:52