Recursion error

[jcarosella10]

I'm writing a simple recursion program that is supposed to find a path through a "maze".

//CLASS MAZESEARCH (driver)
public class MazeSearch
{
    public static void main(String[] args)
    {
        Maze labyrinth = new Maze();
        System.out.println(labyrinth);
        if(labyrinth.traverse(0, 0))
        {
            System.out.println("The maze was successfully solved!");
        }
        else
        {
            System.out.println("There is no possible path.");
        }
        System.out.println(labyrinth);
    }
}
//CLASS MAZE
public class Maze
{
    private final int TRIED = 3;
    private final int PATH = 7;
    private int[][] grid = {    {1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1},
                                {1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
                                {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
                                {1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
                                {1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
                                {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
                                {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    public boolean traverse(int row, int column)
    {
        boolean done = false;
        if(valid(row, column))
        {
            grid[row][column] = TRIED;
            if(row == grid.length - 1 && column == grid[0].length - 1)
            {
                done = true;
            }
            else
            {
                done = traverse(row + 1, column + 1);
                if(!done)
                {
                    done = traverse(row, column + 1);
                }
                if(!done)
                {
                    done = traverse(row - 1, column);
                }
                if(!done)
                {
                    done = traverse(row, column - 1);
                }
            }
            if(done)
            {
                grid[row][column] = PATH;
            }
        }
        return done;
    }
    private boolean valid(int row, int column)
    {
        boolean result = false;
        if(row >= 0 && row < grid.length && column >= 0 && column < grid[row].length)
        {
            if(grid[row][column] == 1)
            {
                result = true;
            }
        }
        return result;
    }
    public String toString()
    {
        String result = "\n";
        for(int row = 0; row < grid.length; row++)
        {
            for(int column = 0; column < grid[row].length; column++)
            {
                result += grid[row][column] + "";
            }
            result += "\n";
        }
        return result;
    }
}

Here is the output:
"1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111

There is no possible path.

3330330003333
1033303333003
0000303030300
1110333030333
1010000333003
1011111103333
1000000000000
1111111111111"

Theres the problem in red...why is it not seeing that 1 below the 3 on the left?

[Norm]

why is it not seeing that 1 below the 3 on the left?

Add some printlns to the code to print out what it is doing so you can see where the execution goes and what the values of variables are as it executes

[ozzyman]

I'm not really sure I understand your code but it just seems like this part:

                done = traverse(row + 1, column + 1);
                if(!done)                {
                    done = traverse(row, column + 1);
                }
                if(!done)                {
                    done = traverse(row - 1, column);
                }
                if(!done)                {
                    done = traverse(row, column - 1);
                }

is meant to search up,down,left and right from a given index in the 2d array...

if thats so, then the first statement is wrong and should look like this:

                done = traverse(row + 1, column);

so that you are checking 'down' and not 'down-right'


looking at your output again it seems like all of the 1's that were converted to 3's were accessible through the down-right path up until where it had stopped.

[jcarosella10]

that worked thanks ozzyman