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);
}

Leave a Reply

Your email address will not be published. Required fields are marked *