Java: Maze Solver

I'm writing code to make a maze solver. Here's the instructions:

1) Write a Maze class with the following requirements:

Takes any two-dimensional array that represents a maze: 0s (zeros) for the walls, and 1s for the available paths.

There will be only one constructor that takes a two-dimensional array

A method named displayMaze should print the maze (bird-view) that shows the walls and the available paths, and the path taken so far (if any)

A method named takeStep that takes one step each time when it is called and displays the maze again. Use the algorithm that checks right turn first. And keeps checking counter-clockwise until finds a path.

A method named findExit runs and finds the solution all the way to the exit and displays the maze showing the suggested path

Assume that entry point of the maze is always the first row (row 0) and the third column (column 2) and the first move direction is south.

Test program is given for your testing

The program should work with any Maze including different size of maze.

My problem is I keep getting stuck in a loop because I dont know how to make it backtrack after it hits a dead end.

Here's my code so far:

public class Maze {

private int[][] maze;

public Maze(int[][] maze)

{

this.maze= maze;

}

public void displayMaze()

{

for (int i = 0;i

{

for(int j = 0; j

{

if (maze[i][j] == 0)

{

System.out.print("#");

}

else if (maze[i][j] == 1)

{

System.out.print(" ");

}

else if (maze[i][j] == 2)

{

System.out.print("@");

}

else if (maze[i][j] == 3)

{

System.out.print("~");

}

}

System.out.println("");

}

System.out.println("");

}

public void takeStep(int i, int j)

{

if (maze[i][j+1] == 0)

{

if (maze[i+1][j] == 0)

{

if (maze[i][j-1] == 0)

{

if (maze[i-1][j] == 0)

{

}

else if (maze[i-1][j] == 1)

{

maze[i-1][j] = 2;

i --;

}

}

else if (maze[i][j-1] == 1)

{

maze[i][j-1] = 2;

j--;

}

}

else if (maze[i+1][j] == 1)

{

maze[i+1][j] = 2;

i++;

}

}

else if (maze[i][j+1] == 1)

{

maze[i][j+1] = 2;

j++;

}

this.displayMaze();

this.takeStep(i, j);

}

}

And my test program:

public class TestMaze {

public static void main(String[] args)

{

int[][] mazeAr = {{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0},

{0,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,1,0},

{0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,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,1,1,1,1,1,1,1,1,1,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0},

{0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,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,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0},

{0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};

Maze maze = new Maze(mazeAr);

maze.takeStep(0, 2);

}

}