CODEWITHSUNDEEP
javaarraysalgorithm
Henry Zhu
Henry Zhu

Reputation: 2618

Arrays for Maze Algorithm not Storing Proper Values

I have everything down in my maze solver, except for the fact that the wasHere array is storing the solution (which is supposed to be stored by the correctPath array). It is also missing marking the end square of the maze. All the wasHere array is supposed to store are the spots that the program has gone to in the maze. The correctPath array has all false values, which is totally unexpected. I am using the recursive method mentioned in Wikipedia: https://en.wikipedia.org/wiki/Maze_solving_algorithm

This is my Maze Solver:

private static int[][] maze = {{2, 2, 2, 2, 1, 2, 2}, 
                               {2, 2, 2, 2, 1, 2, 2}, 
                               {2, 2, 2, 2, 1, 2, 2}, 
                               {2, 1, 1, 1, 1, 1, 1}}; // The maze
private static boolean[][] wasHere = new boolean[4][7];
private static boolean[][] correctPath = new boolean[4][7]; // Solution

private static int startX = 4;
private static int startY = 0;

private static int endX = 1;
private static int endY = 3;

public static void main(String[] args) {
    System.out.println("Maze: ");
    printMaze(maze);

    solveMaze();

    boolean b = recursiveSolve(startX, startY); // Whether or not there is a solution to the maze
}

public static void solveMaze()
{
    for (int row = 0; row < maze.length; row++)
    {
        // Sets boolean arrays to false
        for (int col = 0; col < maze[row].length; col++)
        {
            wasHere[row][col] = false;
            correctPath[row][col] = false;
        }
    }
}

public static void printMaze(int[][] array)
{
    for (int row = 0; row < array.length; row++)
    {
        for (int col = 0; col < array[row].length; col++)
        {
            System.out.print(array[row][col]);

            if (col == array[row].length - 1)
            {
                System.out.print("\n");
            }
        }
    }       

    System.out.print("\n");
}

public static void printPath(boolean[][] array)
{
    for (int row = 0; row < array.length; row++)
    {
        for (int col = 0; col < array[row].length; col++)
        {
            if (array[row][col] == true)
            {
                System.out.print("1");
            }
            else
            {
                System.out.print("2");
            }

            if (col == array[row].length - 1)
            {
                System.out.print("\n");
            }
        }
    }
}

public static boolean recursiveSolve(int x, int y)
{
    if (x == endX && y == endY) // Reach end
    {
        System.out.println("The maze is solvable.");
        printPath(wasHere);
        return true;
    }

    if (maze[y][x] == 2 || wasHere[y][x] == true) // Hit a dead end or end up in same place (no solution)
    {
        return false;
    }

    wasHere[y][x] = true;

    if (x != 0) // On left edge or not
    {
        if (recursiveSolve(x - 1, y))
        {
            correctPath[y][x] = true;
            return true;
        }
    }

    if (x != maze[0].length - 1) // On right edge or not
    {
        if (recursiveSolve(x + 1, y))
        {
            correctPath[y][x] = true;
            return true;
        }
    }

    if (y != 0) // On top edge or not
    {
        if (recursiveSolve(x, y - 1))
        {
            correctPath[y][x] = true;
            return true;
        }
    }

    if (y != maze.length - 1) // On bottom edge or not
    {
        if (recursiveSolve(x, y + 1))
        {
            correctPath[y][x] = true;
            return true;
        }
    }

    System.out.println("The maze is not solvable.");
    return false;
}

Upvotes: 0

Views: 91

Answers (1)

sstan
sstan

Reputation: 36473

Your maze solver is working correctly. The problem is that you were probably printing the values of the correctPath array before your recursive method had finished writing to it.

I assume that where you had the following lines inside the recursiveSolve(int x, int y) method:

    System.out.println("The maze is solvable.");
    printPath(wasHere);

... at some point, you tried to run it using the correctPath variable instead, right? Something like this?

    System.out.println("The maze is solvable.");
    printPath(correctPath);

But that is too soon. The correctPath array values are set after the recursive calls start returning from the end of the maze.

Instead, try moving the printPath call after the top level call to the recursiveSolve method inside your main(). Like this:

public static void main(String[] args) {
    System.out.println("Maze: ");
    printMaze(maze);

    solveMaze();

    boolean b = recursiveSolve(startX, startY); // Whether or not there is a solution to the maze

    // Put this here!  It will work as expected.
    System.out.println();
    printPath(correctPath);
}

If this doesn't quite make sense to you, then it probably means that you haven't quite grasped how recursion works. Use a debugger to step through your program, as you should have done in the first place, and things should become clearer.

Upvotes: 1

Related Questions