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:

- Check if the current cell is our destination, if yes, the maze is solved.
- 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.
- 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); }