Recursive Maze Algorithm
Recursive Maze Algorithm is one of the best examples for backtracking algorithms. Recursive Maze Algorithm is one of the possible solutions for solving the maze.
Maze
The maze is an area surrounded by walls; in between, we have a path from starting point to ending position. We have to start from the starting point and travel towards from ending point.
Principle of Maze
As explained above, in the maze we have to travel from starting point to ending point. The problem is to choose the path. If we find any dead-end before ending point, we have to backtrack and move the direction. The direction for traversing is North, East, West, and South. We have to continue “move and backtrack” until we reach the final point.
Consider that we are having a two-dimensional maze cell [WIDTH] [HEIGHT]. Here cell [x] [y] = 1 denotes wall and cell [x] [y] = 0 denotes free cell in the particular location x, y in the maze. The directions we can change in the array are North, East, West, and South. The first step is to make the boundary of the two – dimensional array as one so that we won’t go out of the maze and usually reside inside the maze at any time.
| Example Maze | ||||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Now start changing from the starting position (since the boundary is filled by 1) and find the next free cell then turn to the next free cell and so on. If we grasp a dead-end, we have to backtrack and make the cells in the path as 1 (wall). Continue the same process till the final point is reached.