public class Maze			// solve a 2D maze
{
	public static void main(String[] args) {						// the maze consists of a 2D 24x24 int array where 0 is a wall, 1 is a path and 2 is the exit
		int[][] maze={
			        {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
					{0,1,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0},
					{0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,1,0,0,1,0,0,0},
					{0,1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0},
					{0,0,1,0,0,1,0,1,1,1,1,0,0,1,0,1,0,0,0,1,1,1,0,0},
					{0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,0,0,1,1,0,1,0,0},
					{0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0},
					{0,1,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0},
					{0,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,0},
					{0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0},
					{0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0},
					{0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,0,0,1,0,0,0},
					{0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0,0},
					{0,0,1,0,0,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0},
					{0,0,1,1,1,1,0,0,0,1,1,1,0,1,0,0,0,1,1,1,0,1,1,0},
					{0,0,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0},
					{0,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,1,1,0},
					{0,0,0,1,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0},
					{0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0},
					{0,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,0,1,1,1,1,1,0,0},
					{0,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0},
					{0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0},
					{0,1,1,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0},
					{0,0,1,0,0,1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,2,0,0}};
		int size=24;
		solve(maze,0,5,size);									// start the recursive call starting at coordinate 0,5, use size to ensure that we don't go beyond the bounds of the array
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++)
				System.out.print(maze[i][j]);					// print out the maze afterward, having changed the path out of the maze from 1s to 3s
			System.out.println();
		}	
	}
		
	public static boolean solve(int[][] m, int x, int y, int s)	// m is the maze, x, y the current coordinate, s the upper bound of the 2D array
	{	
		if(x>=s||x<0||y>=s||y<0) return false;					// if out of bounds, return false
		else if(m[x][y]==3) return false;						// if we reach a 3, we've tried that path already so we are in a loop, return false
		else if(m[x][y]==2) return true;						// if we reach a 2 then we found the solution, return true
		else if(m[x][y]==0) return false;						// if we reach a 0, we hit a wall, return false
		else
		{
			m[x][y]=3;											// assume this is the right path, set this location to 3 to record where we are
			if (solve(m,x+1,y,s)) return true;					// recursive try to solve from this point forward by trying down, up, right then left
			if (solve(m,x-1,y,s)) return true;					// we try the next location from x,y if the previous one was not true (that is, did not lead to a solution)
			if (solve(m,x,y+1,s)) return true;
			if (solve(m,x,y-1,s)) return true;
			m[x][y]=1;											// starting at x,y, we could not find a way out, so reset this location to 1 and return false
			return false;
		}
	}
}