Maze Recursion Code Finishes Maze but Returns Errors

Question

I would appreciate any help in figuring out the error in my code.

I'm working on a recursion maze project for my Java class and have gotten completely stuck. The maze finishes and displays the steps it took successfully but then it returns a ton of errors at the end.

The algorithm is under the mazeTraversal function.

Thank you.

public class Maze {
   static final int DOWN = 0;
   static final int RIGHT = 1;
   static final int UP = 2;
   static final int LEFT = 3;
   static final int ROW_START = 2;
   static final int COLUMN_START = 0;
   static int move = 0;
   static char maze[][] =
      { { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
        { '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
        { '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' },
        { '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.' },
        { '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
        { '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' },
        { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };


   // method calls mazeTraversal with correct starting point and direction
   public void traverse() {
      boolean result = mazeTraversal( ROW_START, COLUMN_START );

      if ( !result )
         System.out.println( "Maze has no solution." );
   } // end method traverse

   // traverse maze recursively
   public boolean mazeTraversal( int row, int column ) {
       // TO BE COMPLETE
                maze[row][column] = 'x';
                printMaze();
                if (column > 0 && maze[row][column - 1] == '.')
                {
                    maze[row][column - 1] = 'x';
                    return mazeTraversal(row, column - 1);
                }
                else if (column <= 11 && maze[row][column + 1] == '.')
                {
                    maze[row][column + 1] = 'x';
                    return mazeTraversal(row, column + 1);
                }
                else if (row > 0 && maze[row - 1][column] == '.')
                {
                    maze[row - 1][column] = 'x';
                    return mazeTraversal(row - 1, column);
                }
                else if (row <= 11 && maze[row + 1][column] == '.')
                {
                    maze[row + 1][column] = 'x';
                    return mazeTraversal(row + 1, column);
                }
                else
                {
                    maze[row][column] = 'o';
                    if (column <= 11 && maze[row][column + 1]  == 'x')
                    {
                        maze[row][column + 1] = 'o';
                        return mazeTraversal(row, column + 1);
                    }
                    else if (column > 0 && maze[row][column - 1] == 'x')
                    {
                        maze[row][column - 1] = 'o';
                        return mazeTraversal(row, column - 1);
                    }
                    else if (row <= 11 && maze[row + 1][column] == 'x')
                    {
                        maze[row + 1][column] = 'o';
                        return mazeTraversal(row + 1, column);
                    }
                    else if (row > 0 && maze[row - 1][column] == 'x')
                    {
                        maze[row - 1][column] = 'o';
                        return mazeTraversal(row - 1, column);
                    }
                }           
               return true;
   } // end method mazeTraversal

   // draw maze
   public void printMaze() {

      // for each space in maze
      for ( int row = 0; row < maze.length; row++ )
      {
         for ( int column = 0; column < maze[ row ].length;
            column++ )
         {
            if ( maze[ row ][ column ] == '0' )
               System.out.print( " ." );
            else
               System.out.print( " " + maze[ row ][ column ] );
         }

         System.out.println();
      } // end for

      System.out.println();
   } // end method printMaze
} // end class Maze

Here are the Errors:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 12

    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
 # . . . . . . # . . . #
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
 # # # # # # # # # # # #

    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:79)
    at Maze.mazeTraversal(Maze.java:79)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.traverse(Maze.java:31)
    at MazeTest.main(MazeTest.java:9)
/Users/user/Library/Caches/NetBeans/8.2/executor-snippets/run.xml:53: Java returned: 1

Answer 1

The <= (less than or equal) operators below are all incorrect, they should simply be < (less than):

else if (column <= 11 && maze[row][column + 1] == '.')
else if (row <= 11 && maze[row + 1][column] == '.')
    if (column <= 11 && maze[row][column + 1]  == 'x')
    else if (row <= 11 && maze[row + 1][column] == 'x')

In addition, you'll need to add an explicit end of maze test (i.e. check for ROW_END and COLUMN_END) otherwise the above change will cause your code to explore and backtrack the entire maze:

static final int ROW_END = 4;
static final int COLUMN_END = 11;

// ...

// traverse maze recursively
public boolean mazeTraversal(int row, int column)
{
    maze[row][column] = 'x';
    printMaze();

    if (column == COLUMN_END && row == ROW_END)
    {
        return true;
    }

    if (column > 0 && maze[row][column - 1] == '.')
    {
        maze[row][column - 1] = 'x';
        return mazeTraversal(row, column - 1);
    }

    if (column < 11 && maze[row][column + 1] == '.')
    {
        maze[row][column + 1] = 'x';
        return mazeTraversal(row, column + 1);
    }

    if (row > 0 && maze[row - 1][column] == '.')
    {
        maze[row - 1][column] = 'x';
        return mazeTraversal(row - 1, column);
    }

    if (row < 11 && maze[row + 1][column] == '.')
    {
        maze[row + 1][column] = 'x';
        return mazeTraversal(row + 1, column);
    }

    maze[row][column] = 'o';

    if (column < 11 && maze[row][column + 1] == 'x')
    {
        maze[row][column + 1] = 'o';
        return mazeTraversal(row, column + 1);
    }

    if (column > 0 && maze[row][column - 1] == 'x')
    {
        maze[row][column - 1] = 'o';
        return mazeTraversal(row, column - 1);
    }

    if (row < 11 && maze[row + 1][column] == 'x')
    {
        maze[row + 1][column] = 'o';
        return mazeTraversal(row + 1, column);
    }

    if (row > 0 && maze[row - 1][column] == 'x')
    {
        maze[row - 1][column] = 'o';
        return mazeTraversal(row - 1, column);
    }

    return true;
} // end method mazeTraversal