Backtrack algorithm, Stack overflow error, despite heap allocation

Question

I'm currently working on a program that has to solve a 10x10 char maze, for example this one:

      1   2   3   4   5   6   7   8   9  10
___________________________________________
 1|   +  []   +  []   +  []   +   +   +  []
 2|   +  []   +   +  []   +   +  []  []  []
 3|   +   +  []  []  []   +  []  []   +   +
 4|  []  []  []  []   +   +   +  []  []   +
 5|   +  []   +  []   +  []   +   +   +  []
 6|   +   +   +   +   +   +  []  []   +  []
 7|  []   +   +   +  []  []   +   +   +  []
 8|   +   +   +  []   +   +   +  []  []   +
 9|   +   +   +  []  []   +   +  []  []   +
10|   +  []   +  []   +   +  []   +   +   +

Ignore the numbers, they are just coordinates. As for [] it's just the way the maze is printed. In actuality wherever there's a + then that means path, wherever there's [] that means there's an obstacle.

I'm using the backtrack algorithm:

void backtrack(int curX, int curY, char(*char_maze)[10], int position)
{
    if (curX < 0 || curY < 0 ||
        curX > 9 || curY > 9) {
        //out of bounds
        return;
    }
    Node tmp;
    tmp.x = curX, tmp.y = curY;
    queue(&head, &tmp);
    position++;
    if (char_maze[curX][curY] == finish) {
        //destination found TODO print path
        printf("route found");
    }
    if (char_maze[curX][curY] == path) {
        char_maze[curX][curY] = visited;
    }
    backtrack(curX, curY - 1, char_maze, position);
    backtrack(curX - 1, curY, char_maze, position);
    backtrack(curX, curY + 1, char_maze, position);
    backtrack(curX + 1, curY, char_maze, position);

    char_maze[curX][curY] = path;
    if (position) {
        del_nth(head, position);
    }
    if (!position) {
        del_first(&head);
    }
    position--;
}

The correct route will consist of a linked list, here's a node of that list:

typedef struct coords {
    int     x;
    int     y;
    struct coords * next;
}Node;

whenever backtrack(...) stumbles over a passable cell, it's supposed to mark it as visited and add it to the list. Adding to the list is done by these 2 functions:

void queue(Node ** head, Node * object)
{
    Node * tmp = (Node *)malloc(sizeof(Node)); //this is the problematic line
    *tmp = *object;
    Node * last = get_last(*(head));
    if (!last) {
        (*head) = tmp;
        tmp->next = NULL;
    }
    else {
        last->next = tmp;
        tmp->next = NULL;
    }
}

and

Node * get_last(Node * head)
{
    while (1) {
        if (head) {
            head = head->next;
        }
        else {
            return NULL;
        }
    }
return head;
}

and also under the appropriate conditions backtrack(...) should unmark a cell and delete it from the list. Deletion is done using these 2 functions:

void del_nth(Node * head, int index)
{
    Node * previous;
    for (int i = 0; i < index - 1; i++) {
        head = head->next;
    }
    previous = head;
    head = head->next;
    previous->next = head->next;
    free(head);
}

and

void del_first(Node ** head)
{
    Node * del = (*head);
    (*head) = (*head)->next;
    free(del);
}

path, visited, finish and so on are const char-s, which represent the cells of the maze.

backtrack(...)

is called with 2 coordinates set by the user, the maze itself and position which is set to 0.

Now that I explained how the code works, the problem. I've ran this code through the Visual Studio Debugger and I got a Stack overflow (parameters: 0x00000001, 0x00492FFC). exception on this line

Node * tmp = (Node *) malloc(sizeof(Node));

which is a part of the queue(...) function. This doesn't make any sense to me, since malloc() allocates on the heap. I'm stumped, I'm out of explanations, I have no idea why this happens. I included all of the code used in the backtrack(...) function because the problem may actually be there. It wouldn't be the first time a debugger pointed out a wrong line. Anyway, many thanks for your help in advance.

If a recursive function is giving you a stack overflow, that's because of the stack frame being created for each recursive call; the heap allocation has nothing to do with it. — Govind Parmar
– Govind Parmar, Commented Feb 11, 2019 at 20:57
You can replace get_last with return NULL since that's what it does. — stark
– stark, Commented Feb 11, 2019 at 21:09
You still call backtrack even when the cell is already visited. You should only call when it is still path. — stark
– stark, Commented Feb 11, 2019 at 21:23
You have no base case in your recursion. You only stop recursing when you go out of bounds, but nothing stops you from going back and forth between two cells. — Barmar
– Barmar, Commented Feb 11, 2019 at 21:43
You need to return immediately when the cell has already been visited. — Barmar
– Barmar, Commented Feb 11, 2019 at 21:43

Michaël Roy · Accepted Answer · 2021-11-18 16:24:03Z

You function should return the path it found. It also should return immediately if the current location is not an open space. It also should stop whenever a solution is found.

HINT: In most recursive algorithms, the return value is used to stop recursion, so recursive functions usually return something of interest, like the result of the operation.

Example:

Node* backtrack(int curX, int curY, char(*char_maze)[10], int position)
{
    Node* node = NULL;

    // return as fast as possible for
    if (curX < 0 || curY < 0 || curX > 9 || curY > 9) 
    {
        return NULL;
    }
    if (position > 100)  // 10 * 10 cells.
    {
        // should not reach this point.
        printf("iteration depth exceeded maximum limit!!\n")
        return NULL;
    }

    if (char_maze[curX][curY] == finish) 
    {
        printf("route found");
        node = malloc(sizeof(Node));
        if (node)
        {
            node->x = curX;
            node->y = curY;
            node->next = NULL;
        }
        else
        {
            printf("*** ERROR *** malloc returns NULL (1)!!!\n");
        }

        return node;  // this return point is what triggers the backtrack chaining
                      // of positions
    }
    if (char_maze[curX][curY] != path) // nothing to do
    {
        return NULL;
    }

    // mark current location as being worked on.
    char_maze[curX][curY] = visited;

    // now try possible moves, stop looking as soon as a path is found.
    if ((node = backtrack(curX, curY - 1, char_maze, position + 1) != NULL
        || (node = backtrack(curX - 1, curY, char_maze, position + 1) != NULL
        || (node = backtrack(curX, curY + 1, char_maze, position + 1) != NULL
        || (node = backtrack(curX + 1, curY, char_maze, position + 1) != NULL)
    {
        // path found, add current position to the head of the list
        Node* p = malloc(sizeof(Node));
        if (p)
        {
            p->x = curX;
            p->y = curY;
            p->next = node;
            node = p;
        }
        else
        {
            // out of memory, free whatever was allocated before returning.
            printf("*** ERROR *** malloc returns NULL (2)!!!\n");
            while (node)
            {
                p = node->next;
                free(node);
                node = p;
            }
        }
    }

    char_maze[curX][curY] = path;  // clean up.

    return node; // return path found (or not found);
}

NOTE: I have not compiled this code, but this should help you complete your program.

Collectives™ on Stack Overflow

Backtrack algorithm, Stack overflow error, despite heap allocation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related