## Solving a maze by backtracking

Input : We are given a 2-D maze. The objective is to navigate our way through the maze and travel from the starting position to the specified end point (the goal position). We are supposed to search for a path from the starting position to the goal position till we either find one or exhaust all possibilities. In addition, we are asked to mark the path we find through the maze. At every step, we can only move one step in either of the following directions

```Up (x,y) -> (x,y-1)
Down (x,y) -> (x,y+1)
Left (x,y) -> (x-1,y)
Right (x,y) -> (x+1,y)```

The problem can be described by the following diagram

Solution : The maze can be represented by a 2D array of characters, where

```private static char[][] maze = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' },
{ '*', 'S', ' ', ' ', ' ', '*', '*', '*', '*', '*' },
{ '*', '*', '*', '*', ' ', ' ', ' ', '*', '*', 'E' },
{ '*', '*', '*', '*', '*', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', ' ', ' ', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', '*', ' ', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ' },
{ '*', '*', '*', ' ', '*', '*', '*', '*', '*', '*' },
{ '*', ' ', ' ', ' ', '*', '*', '*', '*', '*', '*' },
{ '*', ' ', '*', '*', '*', '*', '*', '*', '*', '*' } };

S = Starting point
E = End point
* = wall```

The natural way of doing it is to start walking in a random direction till we encounter a end dead. At this point, we retrace our steps back and try a different direction. Once we find out that a particular sequence of steps lead to a dead end, we never take that path again. If we keep following this method, we would eventually reach the specified end point. This is a classic example of backtracking. We will build our solution path one step at a time. After every step, we will recursively solve the remaining maze. If we encounter a dead end, we will backtrack and try a different path.

First we need a way to move through the maze. There are four possible directions we can move : up,down,left and right. Let us represent these four directions through two arrays.

```static private int[] movesX = {-1,0,1,0};
static private int[] movesY = {0,-1,0,1};```

These arrays represent the change in coordinate when we move left,up,right or down respectively. For example, if we want to move up from our current position, we do

```curX = curX + movesX[1]
curY = curY + movesY[1]```

Now that we have a way of moving around the maze, let's discuss about our strategy to remember the current partial solution path. At every point, we should be able to trace our way back to the starting position. This is important for two reasons

1. We need to print the whole path once we successfully solve the maze
2. While selecting the next step, we need to make sure that we don't try to go to a position that is already a part of our current solution path.

We can use a 2D boolean array to keep track of the steps we've taken. This 2D array will store the current partial solution path.

So our algorithm is something like this

1. pick a direction to move
2. calculate the new position if we were to move in that direction
3. check if that position is 'safe'. A position is safe when -

a. It is within the maze
b. It is not blocked by a wall
c. It is not a part of the current solution path

4. If it is, recursively solve the maze from that position
5. if it's not, go back to step 1 and pick a new direction to move

Here is the pseudocode,

```func solveMaze(x,y,record)
if( reached end point )
print solution
return
else
for every direction up,down,left and right
calculate new X,Y coordinates
if( new )
mark newX,newY as part of the current partial solution path
solveMaze( newX, newY, record)
If we reach this line, that means (newX,newY) is not a part of the final solution path. So unmark newX,newY (back track)```

The implementation in Java

```public class Maze {
private static int MAX_X = 10, MAX_Y = 10;
static private int[] movesX = { -1, 0, 1, 0 };
static private int[] movesY = { 0, -1, 0, 1 };
private static boolean[][] record = new boolean[MAX_X][MAX_Y];

private static char[][] maze = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' },
{ '*', 'S', ' ', ' ', ' ', '*', '*', '*', '*', '*' },
{ '*', '*', '*', '*', ' ', ' ', ' ', '*', '*', 'E' },
{ '*', '*', '*', '*', '*', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', ' ', ' ', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', '*', ' ', '*', ' ', '*', '*', ' ' },
{ '*', '*', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ' },
{ '*', '*', '*', ' ', '*', '*', '*', '*', '*', '*' },
{ '*', ' ', ' ', ' ', '*', '*', '*', '*', '*', '*' },
{ '*', ' ', '*', '*', '*', '*', '*', '*', '*', '*' } };

public void resetRecord() {
for (int i = 0; i < MAX_X; i++) {
for (int j = 0; j < MAX_Y; j++) {
record[i][j] = false;
}
}
}

public void showPath() {
for (int i = 0; i < MAX_X; i++) {
for (int j = 0; j < MAX_Y; j++) {
if (record[i][j] && maze[i][j] != 'S' && maze[i][j] != 'E') {
System.out.printf(" %1s ", "-");
} else if (maze[i][j] == ' ') {
System.out.printf(" %1s ", " ");
} else if (maze[i][j] == 'S') {
System.out.printf(" %1s ", "S");
} else if (maze[i][j] == 'E') {
System.out.printf(" %1s ", "E");
} else {
System.out.printf(" %1s ", "*");
}
}
System.out.println(" ");
}
}

public void showMaze() {
for (int i = 0; i < MAX_X; i++) {
for (int j = 0; j < MAX_Y; j++) {
System.out.print(maze[i][j]);
}
System.out.println(" ");
}
}

public boolean isSafe(boolean[][] record, int x, int y) {
if (x < 0 || x >= MAX_X || y < 0 || y >= MAX_Y) {
return false;
}
if (maze[x][y] == '*') {
return false;
}
if (record[x][y] == true) {
return false;
}
return true;
}

public boolean solveMaze(char[][] maze, boolean[][] record, int x, int y) {
if (maze[x][y] == 'E') {
System.out.println(" ");
record[x][y] = true;
showPath();
return true;
} else {
for (int i = 0; i < 4; i++) {
if (isSafe(record, x + movesX[i], y + movesY[i])) {
record[x + movesX[i]][y + movesY[i]] = true;
if (solveMaze(maze, record, x + movesX[i], y + movesY[i])) {
return true;
}
record[x + movesX[i]][y + movesY[i]] = false;
}
}
}
return false;
}

public void start() {
int flag = 0, start_x = 0, start_y = 0;
resetRecord();
for (int i = 0; i < MAX_X; i++) {
for (int j = 0; j < MAX_Y; j++) {
if (maze[i][j] == 'S') {
flag = 1;
start_x = i;
start_y = j;
break;
}
if (flag == 1) {
break;
}
}
}
if (!solveMaze(maze, record, start_x, start_y)) {
System.out.println("cant solve this maze");
}
}

public static void main(String args[]) {
Maze m = new Maze();
m.showPath();
m.start();
}
}
```

Algorithm 12 maze 12