Solve maze backtracking

**rmmstn** · 04-12-2021

I'm trying to solve a maze from 'S' to 'E', then printing the solution with a '.' in each cell from the path. The maze is:

Code:

################################################################################
#S                                                                  #          #
################################################################### # ######## #
#                                                           ####### # ##    ## #
# ######################################################### #       # ## ## ## #
# # #E                                                    # ####### # ## ## ## #
# # ##################################################### #         # ## #  ## #
# #                                                       ######### # ## ## ## #
# ####################################################### # #       # ## ## ## #
# #                                                         # ##### # ## ## ## #
# # ####################################################### # # ### # ## ## ## #
# # #        #########################                      # #     # ## ## ## #
# # # ######                         ######################## ##### # ## ## ## #
# # # ## ### ####################### # ##     ###     ##    ##    # # ## ## ## #
# # #  #     #                       #    ###     ###    ##    #### # ## ## ## #
# # ## ############################# # ############################ # ## ## ## #
# # ## #                        ###  #                            # # ## ## ## #
# # ## # ########### ############   ## ############################## ## ## ## #
# #    #           # #            ####                                #  ###   #
# ################ # ####### ######### ##############################   #### # #
#                # # #                                            # ########## #
######## ######### # ############################################## #          #
#                  #                                                  ### ######
################################################################################

My code so far:

Code:

#include <stdio.h>#include <stdlib.h>
#include <stdbool.h>


#define MAX 1000
#define HEIGHT 24
#define WIDTH 81


void storeMaze(int N, int M, int matrix[N][M], FILE *fp);
int countLines(FILE *fp);
int countColumns(FILE *fp);
void back(int step);
bool isSolution(int x_next, int y_next);




int dx[4]= {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int start_x, start_y, end_x, end_y;




int main(int argc, char **argv)
{
    if(argc != 2)
    {
        fprintf(stderr, "Invalid format.\nCorrect format: %s maze_file.dat\n", argv[0]);
        exit(EXIT_FAILURE);
    }


    FILE *fin = fopen(argv[1], "rb");


    if(!fin)
    {
        fprintf(stderr, "Couldn't open file: %s\n", argv[1]);
        exit(EXIT_FAILURE);
    }


    int N = countLines(fin); // lines in the matrix
    rewind(fin);
    int M = countColumns(fin); // columns in the matrix
    rewind(fin);
//  printf("Lines: %d | Columns: %d\n", N, M);
    int maze[N][M];
	int sol[N][M];
    storeMaze(N, M, maze, fin);
//	printf("Lines: %d | Columns: %d\n", N, M);//24 81


    fclose(fin);


    return 0;
}


void storeMaze(int N, int M, int matrix[N][M], FILE *fp)
{
    int z=0, i;
    char buf[1000];


	while (fgets(buf, sizeof buf, fp))
	{
 		for(i = 0; buf[i] != '\n' && z < N; i++)
		{
			if(buf[i] == '#')
        	{
        		matrix[z][i] = 0;
				putchar('#');
        	}
        	else if(buf[i] == ' ')
        	{
        		matrix[z][i] = 1;
				putchar(' ');
        	}
			else if(buf[i] == 'S')
			{
				start_x = z;
				start_y = i;
				matrix[z][i] = 2;
				putchar('S');
			}
			else if(buf[i] == 'E')
			{
				end_x = z;
				end_y = i;
				matrix[z][i] = 3;
				putchar('E');
			}


     		//printf("%d ", matrix[z][i]);
		}
		putchar('\n');
      	z++;


    }
    putchar('\n');
	printf("The starting point: (%d,%d)\n", start_x, start_y);
	printf("The end point: (%d,%d)\n", end_x, end_y);
}


int countLines(FILE *fp)
{
    char c;
    int count = 0;
    while((c = fgetc(fp)) != EOF)
    {
        if (c == '\n') // Increment count if this character is newline
        {
            count++;
        }
    }
    return count;
}


int countColumns(FILE *fp)
{
    char c;
    int count = 0;
    while((c = fgetc(fp)) != EOF)
    {
        if (c == '\n') // Increment count if this character is newline
        {
            break;
        }
        count++;
    }
    return count;
}


void back(int step)
{
	int v, x_next, y_next, maze[HEIGHT][WIDTH];
	int x_current = start_x, y_current = start_y;


	for(v = 0; v < 4; v++)
	{
		x_next = x_current + dx[v];
		y_next = y_current + dy[v];
		if(x_next >= 0 && y_next >= 0 && x_next < HEIGHT && y_next < WIDTH) //check not to overstep matrix
		{
			x_current = x_next;
			y_current = y_next;
			maze[x_current][y_current] = ' ';
			if(isSolution(x_next, y_next) == true)
			{
				printf("Solution found\n");
			}
		}
		x_current = x_current - dx[v]; // redo the movement if it's not valid
		y_current = y_current - dy[v];
		maze[x_current][y_current] = 0; // put a wall here to not return after backtracking
	}
}


bool isSolution(int x_next, int y_next)
{
	if((x_next == end_x) && (y_next == end_y))
		return true;
	else
		return false;
}

I've successfully stored the maze inside the matrix, however, I can't use the sizes in other functions, unless I define them as macros. Can I change this?
Also, instead of the back function, I also saw algorithms using something like:

Code:

bool findPath(char maze[WIDTH][HEIGHT], int x, int y) {


    maze[x][y] = 'h';


    if (x == WIDTH - 1 && y == HEIGHT - 1) {
        return true;
    }


    if (x + 1 < WIDTH && maze[x + 1][y] == ' ') {
        if (findPath(maze, x + 1, y)) {
            return true;
        }
    }


    if (x - 1 >= 0 && maze[x - 1][y] == ' ') {
        if (findPath(maze, x - 1, y)) {
            return true;
        }
    }


    if (y + 1 < HEIGHT && maze[x][y + 1] == ' ') {
        if (findPath(maze, x, y + 1)) {
            return true;
        }
    }


    if (y - 1 >= 0 && maze[x][y - 1] == ' ') {
        if (findPath(maze, x, y - 1)) {
            return true;
        }
    }


    maze[x][y] = ' ';


    return false;
}


void printMaze(char maze[WIDTH][HEIGHT]) {


    for (int i = 0; i < WIDTH; i++) {
            for (int j = 0; j < HEIGHT; j++) {
                    printf("%c ", maze[i][j]);
        }
        putchar('\n');
    }
}

But I get invalid type warnings if I try to call these in main, using the maze with sizes N and M. Which one would be better to use and how can I solve the issues?

**rmmstn** · 04-13-2021

I've updated the code:

Code:

[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]include[/COLOR] [COLOR=var(--highlight-variable)]<stdio.h>[/COLOR][/COLOR]
[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]include[/COLOR] [COLOR=var(--highlight-variable)]<stdlib.h>[/COLOR][/COLOR]
[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]include[/COLOR] [COLOR=var(--highlight-variable)]<stdbool.h>[/COLOR][/COLOR]


[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]define[/COLOR] MAX 1000[/COLOR]
[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]define[/COLOR] HEIGHT 24[/COLOR]
[COLOR=var(--highlight-keyword)]#[COLOR=var(--highlight-keyword)]define[/COLOR] WIDTH 81[/COLOR]

[COLOR=var(--highlight-keyword)]void[/COLOR] [COLOR=var(--highlight-literal)]storeMaze[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] N, [COLOR=var(--highlight-keyword)]int[/COLOR] M, [COLOR=var(--highlight-keyword)]int[/COLOR] matrix[N][M], FILE *fp);
[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]countLines[/COLOR](FILE *fp);
[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]countColumns[/COLOR](FILE *fp);
[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]find_path[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] x, [COLOR=var(--highlight-keyword)]int[/COLOR] y, [COLOR=var(--highlight-keyword)]int[/COLOR] maze[HEIGHT][WIDTH]);
[COLOR=var(--highlight-keyword)]void[/COLOR] [COLOR=var(--highlight-literal)]printMaze[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] maze[HEIGHT][WIDTH]);


[COLOR=var(--highlight-keyword)]int[/COLOR] start_x, start_y, end_x, end_y;




[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]main[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] argc, [COLOR=var(--highlight-keyword)]char[/COLOR] **argv)
{
    [COLOR=var(--highlight-keyword)]if[/COLOR](argc != [COLOR=var(--highlight-namespace)]2[/COLOR])
    {
        [COLOR=var(--highlight-literal)]fprintf[/COLOR]([COLOR=var(--highlight-literal)]stderr[/COLOR], [COLOR=var(--highlight-variable)]"Invalid format.\nCorrect format: %s maze_file.dat\n"[/COLOR], argv[[COLOR=var(--highlight-namespace)]0[/COLOR]]);
        [COLOR=var(--highlight-literal)]exit[/COLOR](EXIT_FAILURE);
    }


    FILE *fin = fopen(argv[[COLOR=var(--highlight-namespace)]1[/COLOR]], [COLOR=var(--highlight-variable)]"rb"[/COLOR]);


    [COLOR=var(--highlight-keyword)]if[/COLOR](!fin)
    {
        [COLOR=var(--highlight-literal)]fprintf[/COLOR]([COLOR=var(--highlight-literal)]stderr[/COLOR], [COLOR=var(--highlight-variable)]"Couldn't open file: %s\n"[/COLOR], argv[[COLOR=var(--highlight-namespace)]1[/COLOR]]);
        [COLOR=var(--highlight-literal)]exit[/COLOR](EXIT_FAILURE);
    }


    [COLOR=var(--highlight-keyword)]int[/COLOR] N = countLines(fin); [COLOR=var(--highlight-comment)]// lines in the matrix[/COLOR]
    rewind(fin);
    [COLOR=var(--highlight-keyword)]int[/COLOR] M = countColumns(fin); [COLOR=var(--highlight-comment)]// columns in the matrix[/COLOR]
    rewind(fin);
[COLOR=var(--highlight-comment)]//  printf("Lines: %d | Columns: %d\n", N, M);[/COLOR]
    [COLOR=var(--highlight-keyword)]int[/COLOR] maze[N][M];
[COLOR=var(--highlight-comment)]//  int sol[N][M];[/COLOR]
    storeMaze(N, M, maze, fin);
    [COLOR=var(--highlight-keyword)]if[/COLOR](find_path(start_x, start_y, maze) == [COLOR=var(--highlight-literal)]true[/COLOR])
    {
        printMaze(maze);
    }
    [COLOR=var(--highlight-keyword)]else[/COLOR]
        [COLOR=var(--highlight-literal)]printf[/COLOR]([COLOR=var(--highlight-variable)]"No solution!\n"[/COLOR]);
[COLOR=var(--highlight-comment)]//  printf("Lines: %d | Columns: %d\n", N, M);//24 81[/COLOR]
    
    
    fclose(fin);


    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-namespace)]0[/COLOR];
}


[COLOR=var(--highlight-keyword)]void[/COLOR] [COLOR=var(--highlight-literal)]storeMaze[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] N, [COLOR=var(--highlight-keyword)]int[/COLOR] M, [COLOR=var(--highlight-keyword)]int[/COLOR] matrix[N][M], FILE *fp)
{
    [COLOR=var(--highlight-keyword)]int[/COLOR] z=[COLOR=var(--highlight-namespace)]0[/COLOR], i;
    [COLOR=var(--highlight-keyword)]char[/COLOR] buf[[COLOR=var(--highlight-namespace)]1000[/COLOR]];


    [COLOR=var(--highlight-keyword)]while[/COLOR] (fgets(buf, [COLOR=var(--highlight-keyword)]sizeof[/COLOR] buf, fp))
    {
        [COLOR=var(--highlight-keyword)]for[/COLOR](i = [COLOR=var(--highlight-namespace)]0[/COLOR]; buf[i] != [COLOR=var(--highlight-variable)]'\n'[/COLOR] && z < N; i++)
        {
            [COLOR=var(--highlight-keyword)]if[/COLOR](buf[i] == [COLOR=var(--highlight-variable)]'#'[/COLOR])
            {
                matrix[z][i] = [COLOR=var(--highlight-namespace)]0[/COLOR];
                [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'#'[/COLOR]);
            }
            [COLOR=var(--highlight-keyword)]else[/COLOR] [COLOR=var(--highlight-keyword)]if[/COLOR](buf[i] == [COLOR=var(--highlight-variable)]' '[/COLOR])
            {
                matrix[z][i] = [COLOR=var(--highlight-namespace)]1[/COLOR];
                [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]' '[/COLOR]);
            }
            [COLOR=var(--highlight-keyword)]else[/COLOR] [COLOR=var(--highlight-keyword)]if[/COLOR](buf[i] == [COLOR=var(--highlight-variable)]'S'[/COLOR])
            {
                start_x = z;
                start_y = i;
                matrix[z][i] = [COLOR=var(--highlight-namespace)]2[/COLOR];
                [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'S'[/COLOR]);
            }
            [COLOR=var(--highlight-keyword)]else[/COLOR] [COLOR=var(--highlight-keyword)]if[/COLOR](buf[i] == [COLOR=var(--highlight-variable)]'E'[/COLOR])
            {
                end_x = z;
                end_y = i;
                matrix[z][i] = [COLOR=var(--highlight-namespace)]3[/COLOR];
                [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'E'[/COLOR]);
            }


            [COLOR=var(--highlight-comment)]//printf("%d ", matrix[z][i]);[/COLOR]
        }
        [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'\n'[/COLOR]);
        z++;


    }
    [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'\n'[/COLOR]);
    [COLOR=var(--highlight-literal)]printf[/COLOR]([COLOR=var(--highlight-variable)]"The starting point: (%d,%d)\n"[/COLOR], start_x, start_y);
    [COLOR=var(--highlight-literal)]printf[/COLOR]([COLOR=var(--highlight-variable)]"The end point: (%d,%d)\n"[/COLOR], end_x, end_y);
}


[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]countLines[/COLOR](FILE *fp)
{
    [COLOR=var(--highlight-keyword)]char[/COLOR] c;
    [COLOR=var(--highlight-keyword)]int[/COLOR] count = [COLOR=var(--highlight-namespace)]0[/COLOR];
    [COLOR=var(--highlight-keyword)]while[/COLOR]((c = fgetc(fp)) != EOF)
    {
        [COLOR=var(--highlight-keyword)]if[/COLOR] (c == [COLOR=var(--highlight-variable)]'\n'[/COLOR]) [COLOR=var(--highlight-comment)]// Increment count if this character is newline[/COLOR]
        {
            count++;
        }
    }
    [COLOR=var(--highlight-keyword)]return[/COLOR] count;
}


[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]countColumns[/COLOR](FILE *fp)
{
    [COLOR=var(--highlight-keyword)]char[/COLOR] c;
    [COLOR=var(--highlight-keyword)]int[/COLOR] count = [COLOR=var(--highlight-namespace)]0[/COLOR];
    [COLOR=var(--highlight-keyword)]while[/COLOR]((c = fgetc(fp)) != EOF)
    {
        [COLOR=var(--highlight-keyword)]if[/COLOR] (c == [COLOR=var(--highlight-variable)]'\n'[/COLOR]) [COLOR=var(--highlight-comment)]// Increment count if this character is newline[/COLOR]
        {
            [COLOR=var(--highlight-keyword)]break[/COLOR];
        }
        count++;
    }
    [COLOR=var(--highlight-keyword)]return[/COLOR] count;
}

[COLOR=var(--highlight-keyword)]int[/COLOR] [COLOR=var(--highlight-literal)]find_path[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] x, [COLOR=var(--highlight-keyword)]int[/COLOR] y, [COLOR=var(--highlight-keyword)]int[/COLOR] maze[HEIGHT][WIDTH])
{
    [COLOR=var(--highlight-comment)]// If x,y is outside maze, return false.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( x < [COLOR=var(--highlight-namespace)]0[/COLOR] || x > HEIGHT - [COLOR=var(--highlight-namespace)]1[/COLOR] || y < [COLOR=var(--highlight-namespace)]0[/COLOR] || y > WIDTH - [COLOR=var(--highlight-namespace)]1[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]false[/COLOR];

    [COLOR=var(--highlight-comment)]// If x,y is the goal, return true.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( maze[y][x] == [COLOR=var(--highlight-namespace)]3[/COLOR] ) [COLOR=var(--highlight-comment)]// 'E' - end point [/COLOR]
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]true[/COLOR];

    [COLOR=var(--highlight-comment)]// If x,y is not open, return false.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( maze[y][x] != [COLOR=var(--highlight-namespace)]1[/COLOR] && maze[y][x] != [COLOR=var(--highlight-namespace)]2[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]false[/COLOR];

    [COLOR=var(--highlight-comment)]// Mark x,y part of solution path.[/COLOR]
    maze[y][x] = [COLOR=var(--highlight-variable)]'.'[/COLOR];

    [COLOR=var(--highlight-comment)]// If find_path North of x,y is true, return true.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( find_path(x, y - [COLOR=var(--highlight-namespace)]1[/COLOR], maze) == [COLOR=var(--highlight-literal)]true[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]true[/COLOR];

    [COLOR=var(--highlight-comment)]// If find_path East of x,y is true, return true.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( find_path(x + [COLOR=var(--highlight-namespace)]1[/COLOR], y, maze) == [COLOR=var(--highlight-literal)]true[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]true[/COLOR];

    [COLOR=var(--highlight-comment)]// If find_path South of x,y is true, return true.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( find_path(x, y + [COLOR=var(--highlight-namespace)]1[/COLOR], maze) == [COLOR=var(--highlight-literal)]true[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]true[/COLOR];

    [COLOR=var(--highlight-comment)]// If find_path West of x,y is true, return true.[/COLOR]
    [COLOR=var(--highlight-keyword)]if[/COLOR] ( find_path(x - [COLOR=var(--highlight-namespace)]1[/COLOR], y, maze) == [COLOR=var(--highlight-literal)]true[/COLOR] ) 
    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]true[/COLOR];

    [COLOR=var(--highlight-comment)]// Unmark x,y as part of solution path.[/COLOR]
    maze[y][x] = [COLOR=var(--highlight-namespace)]0[/COLOR]; [COLOR=var(--highlight-comment)]// mark this as a wall[/COLOR]

    [COLOR=var(--highlight-keyword)]return[/COLOR] [COLOR=var(--highlight-literal)]false[/COLOR];
}

[COLOR=var(--highlight-keyword)]void[/COLOR] [COLOR=var(--highlight-literal)]printMaze[/COLOR]([COLOR=var(--highlight-keyword)]int[/COLOR] maze[HEIGHT][WIDTH]) {


    [COLOR=var(--highlight-keyword)]for[/COLOR] ([COLOR=var(--highlight-keyword)]int[/COLOR] i = [COLOR=var(--highlight-namespace)]0[/COLOR]; i < HEIGHT; i++) {
            [COLOR=var(--highlight-keyword)]for[/COLOR] ([COLOR=var(--highlight-keyword)]int[/COLOR] j = [COLOR=var(--highlight-namespace)]0[/COLOR]; j < WIDTH; j++) {
                    [COLOR=var(--highlight-literal)]printf[/COLOR]([COLOR=var(--highlight-variable)]"%d "[/COLOR], maze[i][j]);
        }
        [COLOR=var(--highlight-literal)]putchar[/COLOR]([COLOR=var(--highlight-variable)]'\n'[/COLOR]);
    }
}

But I'm not getting any solution.

**Salem** · 04-13-2021

> void storeMaze(int N, int M, int matrix[N][M], FILE *fp);
If you can do this,

then you should be able to do this
bool findPath(int N, int M, char maze[N][M], int x, int y)

But I would suggest you start with the simplest non-trivial maze possible for your initial tests.

Code:

int main ( ) {
  char maze[][7] = {
    "######",
    "#S   #",
    "### ##",
    "###E##",
    "######",
  };
  solve(5,7,maze);
}

All the elements of
- moving forward
- finding a choice point
- backtracking when you find a dead end
are covered in this really simple example.

If it works with this, then your 70x50 or however large maze is should stand a chance.

Thread: Solve maze backtracking

Thread Tools

Search Thread

Display

Solve maze backtracking

Similar Threads

solve a maze

labyrinth(it's dubbed as numeric maze matrix-backtracking)

Solve a maze recursive

about the backtracking method and maze

Maze game, complete with maze editor and an example maze!

Tags for this Thread