# Backtracking to solve a maze in C

Solving a maze in C is one of the popular problems that utilizes backtracking (Also known as “Rat in a maze” problem).

A maze is a 2D matrix consisting of walls and free cells. One of the cells is a start cell or source cell (basically a starting point). And there is also a finish cell, where we have to reach. Our goal is to find the path from the source to the destination without stepping onto wall.

Here what a some maze or labyrinth looks like in a character representation:

``````#.###########
#.#.........#
#.###.#.###.#
#.....#...#.#
#####.#####.#
#...........#
####.########
#.........#.#
###.#.###.#.#
#...#...#...#
#####.#####.#
#.........#.#
###########.#``````

‘#’ represents blocked cells and ‘.’ represents free cells.

We can use this character representation to load maze into our code more easily but first let’s look how we will actually solve a maze.

## Algorithm

The first step is to create a two dimensional array which will store our maze.

```int main() {

//Static array for our maze
int maze[MAX][MAX];

//Static array for the solution
int sol[MAX][MAX];

//Width and height of our maze
int width = 0, height = 0;

//File pointer
FILE * fp = fopen("maze.txt", "r");

//Helper variable for reading line by line from a file
char line[MAX];

/* This loop will load our maze character by character
and replace each '#' with 1 and '.' with 0 */

while (fscanf(fp, "%s", line) > 0) {
width = strlen(line);
for (int i = 0; i < width; i++) {
if (line[i] == '#')
maze[height][i] = 1;
else
maze[height][i] = 0;

//Set cells in solution to zero
sol[height][i] = 0;
}
height++;
}

if (solve(maze, sol, width, height, 0, 1))
printSolution(sol, width, height);
else
printf("No solution\n");

//Safely close file
fclose(fp);
}```

Once loaded, the matrix will look like this:

``````1011111111111
1010000000001
1011101011101
1000001000101
1111101111101
1000000000001
1111011111111
1000000000101
1110101110101
1000100010001
1111101111101
1000000000101
1111111111101``````

The zero in the upper line is our start cell and the zero in the last line is our destination cell.

Next, we will find a path from the source cell to the destination cell using this algorithm:

1. Check if the current cell is our destination, if yes, the maze is solved.
2. If not, then we will try to move in all 4 direction possible. But the cell we are about to move on must not be a wall and must not be present in our path already. And we will also check if the coordinates are inside the maze.
3. If none of the four moves (down, right, up, or left) are possible, we will simply move back and change our current path (backtracking).

Full code:

```#include <stdio.h>
#include <string.h>

#define MAX 100

// Funtion to solve a maze using backtracking
int solve(int maze[MAX][MAX], int sol[MAX][MAX], int width, int height, int x, int y)
{
//Check if the current cell is our destination
if (x == width - 1 && y == height - 2)
{
//If yes mark it as a path and return true
sol[x][y] = 1;
return 1;
}

// Check if the current cell is within the boundaries of our matrix,
// also make sure it is not a wall and it is not in our path already
if (x >= 0 && y >= 0 && y < width && x < height && maze[x][y] == 0 && sol[x][y] == 0)
{
//if safe to visit then visit the cell
sol[x][y] = 1;

//go down
if (solve(maze, sol, width, height, x, y + 1))
return 1;
//go right
if (solve(maze, sol, width, height, x + 1, y))
return 1;
//go up
if (solve(maze, sol, width, height, x, y - 1))
return 1;
//go left
if (solve(maze, sol, width, height, x - 1, y))
return 1;
//backtracking
sol[x][y] = 0;
return 0;
}

return 0;
}

void printSolution(int sol[MAX][MAX], int width, int height)
{
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
printf("%d", sol[i][j]);
}
printf("\n");
}
}

int main() {

//Static array for our maze
int maze[MAX][MAX];

//Static array for the solution
int sol[MAX][MAX];

//Width and height of our maze
int width = 0, height = 0;

//File pointer
FILE * fp = fopen("maze.txt", "r");

//Helper variable for reading line by line from a file
char line[MAX];

/* This loop will load our maze character by character
and replace each '#' with 1 and '.' with 0 */

while (fscanf(fp, "%s", line) > 0) {
width = strlen(line);
for (int i = 0; i < width; i++) {
if (line[i] == '#')
maze[height][i] = 1;
else
maze[height][i] = 0;

//Set cells in solution to zero
sol[height][i] = 0;
}
height++;
}

if (solve(maze, sol, width, height, 0, 1))
printSolution(sol, width, height);
else
printf("No solution\n");

//Safely close file
fclose(fp);
}```