Trying to replicate a maze algorithm

Question

I'm trying to make my C program solve a maze, using backtracking.

Basically, what the program does is taking a file inserted as a command line argument (the file should contain the maze structure) and try to "solve it", outputting each step made.

The maze-walls are hashtags (#), and the program should avoid them. Every step made should be marked with dot (.). The program can only step on spaces ( ).

The maze starts from the symbol S (Start), and should reach the symbol E (End).

An example of how a maze should look like is like this:

The maze data is stored in a matrix a[1000][1000], 1000 defined as MAX in my program. Every time I make a step on a certain position on the matrix a[y][x], a[y][x] should be transformed into a dot (.).

I'm using the usleep() function, to output the matrix every 80 000 nanoseconds, so that the user can see every step properly.

Everything works (almost fine). When the maze reaches a certain point when it cannot go further, it deletes all the previous steps until it finds another way. The problem is, it deletes more "dots" than it is intended to delete. And (I think) this is the reason it'll never get to the E point.

Information about the code:

These are my global variable declarations:

int i_MAX, j_MAX;

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

where i_MAX and j_MAX are used to compute the size of the maze array a.

The main() function only contains the procedure of procuring the file from the command-line argument, together with computing i_MAX and j_MAX, and also the call back(0).

These are the functions that (in my opinion) cause trouble:

int is_acceptable(int step_Y, int step_X, int i, char a[MAX][MAX]) {
    // check if it is possible to move the current point (step_X, step_Y)
    // to the position (step_X+dx[i], step_Y+dy[i])
    step_Y += dy[i];
    step_X += dx[i];
    if (a[step_Y][step_X] == ' ' && step_Y >= 0 && step_X >= 0 
                                 && step_Y < i_MAX && step_X < j_MAX)
        return 1;
    return 0;
}

int is_solution(int step_Y, int step_X) {
    if (step_Y == i_MAX && step_X == j_MAX) return 1;
    return 0;
}

void bck(int step_Y, int step_X, char a[MAX][MAX]) {
    // test
    system("clear");
    for (int w = 0; w<i_MAX; w++) {
            for(int x = 0; x<j_MAX; x++)
            putchar(a[w][x]);
        printf("\n");
    }
    usleep(80000);
    // end test
    for (int i = 0; i<=3; i++) {
        if (is_acceptable(step_Y, step_X, i, a)) {
            step_Y += dy[i];
            step_X += dx[i];
            a[step_Y][step_X] = '.';
            if (is_solution(step_Y, step_X)) {
                for (int w = 0; w<i_MAX; w++) {
                    for(int x = 0; x<j_MAX; x++)
                        putchar(a[w][x]);
                printf("\n");
                }
            }
            else bck(step_Y, step_X, a);
            a[step_Y][step_X] = ' ';
        }
    }
}

I am pretty sure the problem lays in the last line of the bck() function, when trying to "reset" the invalid position:

a[step_Y][step_X] = ' ';

I tried changing that line in numerous ways, although I still couldn't make the program work properly.

What am I doing wrong? Does it have to do with some other part of the code?

P.S. here's my maze text:

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

Answer 1

• Function : is_solution

E (end) is not necessarily i_MAX and j_MAX. In your example, it is step_Y=5 and step_X=5

• Function: bck

Recursive problem : You change step_X ans step_Y before recursively calling bck. But, if this way is a cul-de-sac, before trying another direction, you have to restore step_X and step_Y to their original values.

void bck (int step_Y, int step_X, char a[MAX][MAX]) {
    // test
    ...
            else bck(step_Y, step_X, a);
            a[step_Y][step_X] = ' ';
            step_Y -= dy[i];
            step_X -= dx[i];
        }
    }
}