Find all possible paths in a maze

Problem

Given a maze where some of the cells are blocked, where left top cell is the entry point and right bottom cell is the exit point, find all possible paths from entry to exit which goes through the non blocked cells.

Solution

For finding all possible paths we do depth first traversal. We mark the start point as visited and then recursively try to find all possible paths form the accessible cells from the first cell. For example suppose we are at some arbitrary cell. We first mark the node, then call the function recursively to all its neighboring cells which are not blocked or marked earlier. If some paths are found from these recursive calls. It prepends current cell to those paths and return the result and unmark the current cell.

Code

import java.util.ArrayList;
import java.util.List;

public class PathInMaze
{
 public static void main(String[] args)
 {
  boolean[][] maze = new boolean[10][10];
  makeRandomMaze(maze);
  printMaze(maze);
  List> paths = findPaths(maze);
  if (paths == null)
  {
   System.out.println("No path possible");
   return;
  }
  for (List path : paths)
  {
   for (Cell cell : path)
    System.out.print(cell + ",");
   System.out.println();
  }
 }

 private static List> findPaths(boolean[][] maze)
 {
  Cell start = new Cell(0, 0);
  Cell end = new Cell(maze.length - 1, maze[0].length - 1);
  List> paths = findPaths(maze, start, end);
  return paths;
 }

 private static List> findPaths(boolean[][] maze, Cell start,
   Cell end)
 {
  List> result = new ArrayList>();
  int rows = maze.length;
  int cols = maze[0].length;
  if (start.row < 0 || start.col < 0)
   return null;
  if (start.row == rows || start.col == cols)
   return null;
  if (maze[start.row][start.col] == true)
   return null;
  if (start.equals(end))
  {
   List path = new ArrayList();
   path.add(start);
   result.add(path);
   return result;
  }
  maze[start.row][start.col] = true;
  Cell[] nextCells = new Cell[4];
  nextCells[0] = new Cell(start.row + 1, start.col);
  nextCells[2] = new Cell(start.row, start.col + 1);
  nextCells[1] = new Cell(start.row - 1, start.col);
  nextCells[3] = new Cell(start.row, start.col - 1);

  for (Cell nextCell : nextCells)
  {
   List> paths = findPaths(maze, nextCell, end);
   if (paths != null)
   {
    for (List path : paths)
     path.add(0, start);
    result.addAll(paths);
   }
  }
  maze[start.row][start.col] = false;
  if (result.size() == 0)
   return null;
  return result;
 }

 private static class Cell
 {
  public int row;
  public int col;

  public Cell(int row, int column)
  {
   this.row = row;
   this.col = column;
  }

  @Override
  public boolean equals(Object obj)
  {
   if (this == obj)
    return true;
   if ((obj == null) || (obj.getClass() != this.getClass()))
    return false;
   Cell cell = (Cell) obj;
   if (row == cell.row && col == cell.col)
    return true;
   return false;
  }

  @Override
  public String toString()
  {
   return "(" + row + "," + col + ")";
  }
 }

 private static void printMaze(boolean[][] maze)
 {
  for (int i = 0; i < maze.length; ++i)
  {
   for (int j = 0; j < maze[i].length; ++j)
   {
    if (maze[i][j])
     System.out.print("#|");
    else
     System.out.print("_|");
   }
   System.out.println();
  }
 }

 private static void makeRandomMaze(boolean[][] maze)
 {
  for (int i = 0; i < maze.length; ++i)
  {
   for (int j = 0; j < maze[0].length; ++j)
   {
    maze[i][j] = (int) (Math.random() * 3) == 1;
   }
  }
  maze[0][0] = false;
  maze[maze.length - 1][maze[0].length - 1] = false;

 }
}