Find all paths in a maze using DFS [duplicate]

Question

Given a source and a destination cell in a maze, I would like to find all possible solutions to a maze using DFS. 0 represents a wall in my maze.

Visualise the maze

I've successfully written a program, but that gives me only one path. I've thought of all the possibilities to extend it to all paths but sadly even after being hours(2 days to be precise) at it, I was unable to come up with a solution.

I thought of keeping a "visited" array for each node so that when I backtrack I don't perform the same move for the previous node. However doing that would only produce a path that is completely distinct(if there is any) with no nodes being the same.

I also thought of some other way but even that posed some problem.

I've also checked out similar questions but none of them are specific to my context. There is a solution using explicit recursion. However, what I want is to use a stack and find all possible paths. Sadly, I couldn't find anything credible(at least in a way that I could understand).

Here's my code for one path.

Edit: I've now implemented the "proper" DFS. I've also added a stack to keep track of the current path. The program then also checks for the unexplored nodes. However, its checking in some other order and therefore I still can get only one path!

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

typedef struct Point
{
    int x,y;
}Point;

typedef struct stack
{
    struct Point pt;
    struct stack* next;
    void push(int, int);
    Point pop();
}stack, stack_path;

stack*front =NULL;
stack_path*front_path =NULL;


void push(int x, int y)
{
    if(front==NULL)
    {
        front = (stack*)malloc(sizeof(stack));
        front -> pt.x = x; front -> pt.y = y;
        front -> next = NULL;
        return;
    }
    stack* temp = (stack*)malloc(sizeof(stack));
    temp -> pt.x = x; temp -> pt.y = y;
    temp -> next = front;
    front = temp;
}

Point pop()
{
    if(front != NULL)
    {
        stack* temp = front;
        Point pt = front -> pt;
        front = front -> next;
        free(temp);
        return pt;  
    }
}

void push_path(int x, int y)
{
    if(front_path==NULL)
    {
        front_path = (stack*)malloc(sizeof(stack_path));
        front_path -> pt.x = x; front_path -> pt.y = y;
        front_path -> next = NULL;
        return;
    }
    stack_path* temp = (stack*)malloc(sizeof(stack_path));
    temp -> pt.x = x; temp -> pt.y = y;
    temp -> next = front_path;
    front_path = temp;
}

Point pop_path()
{
    if(front_path != NULL)
    {
        stack_path* temp = front_path;
        Point pt = front_path -> pt;
        front_path = front_path -> next;
        free(temp);
        return pt;  
    }
}

bool inMaze(Point pt)
{
    return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.y<6);
}


int main()
{

    struct Point pt1;

    int visited[30]={0};
    push(0,0);
    push_path(0,0);

    struct Point dest = {3,4};
    int maze[5][6] = {{1,0,1,1,1,1},
                      {1,0,1,0,1,1},
                      {1,1,1,0,1,1},
                      {0,0,0,0,1,0},
                      {1,1,1,0,1,1}};
    int paths[30]={0};
    int dx[4]={-1, 0, 0, 1};
    int dy[4]={0,-1, 1, 0};
    while(front!=NULL)
    {
        Point pt = pop();

        if(pt.x==dest.x && pt.y==dest.y)
        {
            push_path(pt.x,pt.y);
            int i;

            visited[6*pt.x+pt.y] = 0;
            stack_path *temp = front_path;
            while(temp!=NULL)
            {
                printf("%d%d ",temp->pt.x, temp->pt.y);
                temp = temp->next;
            }
            printf("\n");
            pop_path();

        }
        else
        {
            if(!visited[6*pt.x+pt.y])
            {
                visited[6*pt.x+pt.y] = 1;
                push_path(pt.x,pt.y);
            }
            int i;
            int flag =0;
            for(i=0; i<4; i++)
            {
                pt1.x = dx[i] + pt.x;
                pt1.y = dy[i] + pt.y;
                if(inMaze(pt1) && maze[pt1.x][pt1.y]==1 && visited[6*pt1.x+ pt1.y]==0) 
                {
                    push(pt1.x,pt1.y);
                    flag = 1;
                }
            }
            if(flag==0)
                pop_path();
        }
    }
    return 0;
}

Can someone please guide me to modify this code such that it finds all paths. Expecting the community's help!

PS: SO currently doesn't allow me to embed images and therefore it has automatically created a link.

PS: This question has been marked as duplicate relating to some other question. For your information, I had gone through that very question before posting my question! If anyone would have read the answer there, you could see it wasn't "accepted"! It just says you need to do "all" permutations! If only one would have bothered to go through the other answer(in the other question), they would have realised that it only applied to moving in north, northeast, or east directions! Moreover, I also had made it pretty clear that I don't want a recursive solution - that's what the other question was using!

Edit 2: Working solution

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

typedef struct Point
{
    int x,y;
}Point;

typedef struct stack
{
    struct Point pt;
    struct stack* next;
    int dir_count;
}stack;

stack*front =NULL;



void push(int x, int y)
{

    stack* temp = (stack*)malloc(sizeof(stack));
    temp -> pt.x = x; temp -> pt.y = y;
    temp -> next = front;
    front = temp;
}

Point pop()
{
    if(front != NULL)
    {
        stack* temp = front;
        Point pt = front -> pt;
        front = front -> next;
        free(temp);
        return pt;  
    }
}

bool inMaze(Point pt)
{
    return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.y<6);
}


int main()
{

    struct Point pt1,pt2;
    struct Point pt = {0,0};

    push(0,0);
    front->dir_count = 0;

    struct Point dest = {3,4};
    int maze[5][6] = {{1,0,1,1,1,1},{1,0,1,0,1,1},{1,1,1,0,1,1},{0,0,0,0,1,0},{1,1,1,0,1,1}};

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

    int flag_pop = 0;
    while(front != NULL)
    {
        if(front->pt.x==dest.x && front->pt.y==dest.y)
        {

            stack* temp = front;
            while(temp != NULL)
            {
                printf("%d%d ", temp->pt.x, temp->pt.y);
                temp = temp->next;
            }
            printf("\n");
            pt = pop();

        }
        else
        {
            int i,k;
            int flag_push =0, count = 0, moves=0;
            for(k=0;k<4;k++)
            {
                pt2.x = dx[k] + front->pt.x;
                pt2.y = dy[k] + front->pt.y;
                if(maze[pt2.x][pt2.y]==0 || !inMaze(pt2) || !(pt.x != pt2.x || pt.y != pt2.y))
                    count++;
            }
            // count of possible moves for each node
            moves = 4-count;
            for(i=0; i<4; i++)
            {
                int flag=0;
                pt1.x = dx[i] + front->pt.x;
                pt1.y = dy[i] + front->pt.y;

                // if moves are exhausted
                if(!(front->dir_count<moves))
                    break;

                if(inMaze(pt1) && maze[pt1.x][pt1.y]==1 && (pt.x != pt1.x || pt.y != pt1.y) )
                {
                    stack* temp = front;
                    while(temp != NULL)
                    {
                        if(temp->pt.x == pt1.x && temp->pt.y == pt1.y)
                        {
                            flag = 1;
                            break;
                        }
                        temp = temp->next;
                    }

                    // if node is not there in the path
                    if(flag==0)
                    {
                        front->dir_count++;
                        push(pt1.x, pt1.y);
                        front -> dir_count = 0;
                        flag_push = 1;
                        break;
                    }   
                }
            }
            // if no move was done
            if(flag_push==0)
            {
                pt = pop();

            }
        }   

    }
    return 0;
}

Laden

What if there is a solution that contains a loop? In that case there are infinitely many solutions, so no way to find or list all of them explicitly. – Poleyn

Please provide needed information as text directly here. Not as a scan of a handwritten scribble on paper. For formatting it, please refer to stackoverflow.com/editing-help – Spiffing

For each point, keep a reference to its predecessor point. To prevent cycles during the DFS, check the next point you are adding to the path is not already in the path -- (if your maze is small, you could use a bitfield). – Decentralize

I have posted a working solution to the question this was marked a dupe of. – Josephjosepha

@Stefan Haustein. Is there any possibility that the "duplicate" mark gets removed? I don't understand why people are so quick to mark questions as duplicate – Laden

@StefanHaustein . I would prefer a purely "stack-only" solution. I do not want to use recursion (I want to try out with stacks)! – Laden

I think the standard procedure would be to post the question again with a link to the duplicate and clearly stating that you want an explicit stack. However, the duplicate mark doesn't seem to stop you from getting help, so I am not sure why it should be a big concern. I'd recommend to update your code here using the suggestions you got so far, so it's simpler to spot what's still missing – Josephjosepha

Ya, sure I would do that in sometime! – Laden

@Arshad-- FYI, there are currently 3 votes to reopen; you just need two more.... – Feodora

@StefanHaustein - I have edited my code. Please guide me further. – Laden

You still don't clear visited on pop() and you haven't added a previous pointer to be able to distinguish alternatives pushed earlier from the current path. When you have found a solution, you need to go back to the closest alternative, skipping nodes on the current path – Josephjosepha

p.s. I see that you are using two stacks instead of a "previous_path_element" pointer in the existing stack elements. I think that might turn out tricky to sync. An alternative to pushing alternatives on the stack might be to keep track of the direction you have taken (0..3) for each stack element, and when you backtrack, increment this number until you are out of options before you pop. This can avoid pushing alternatives, and you'd need a path stack only. – Josephjosepha

@StefanHaustein - I have solved the question, but without explicitly using any prev pointer! Please suggest further improvements if any! – Laden

@StefanHaustein - I have solved this only with this very statement of yours - "An alternative to pushing alternatives on the stack might be to keep track of the direction you have taken (0..3) for each stack element" – Laden

The maze { { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }, { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 }, } has an optimal solution of length 12 but the code isn't printing anything shorter than 14 steps. What might the issue be? – Aedes

Answer 1

I think you need to clear the corresponding field in visited where you remove the point from the stack.

Edit: Another issue is that you need to backtrack when you have reached the goal. And on your stack, it's probably not obvious what unexplored alternatives are and what the current path is (you might be able to use the visited array to track this, but it seems more convoluted than "just" using recursion or adding the corresponding information to your Stack stuct)

Also, subsequent nodes should be marked visited when they are actually investigated, not when they are pushed on the stack.

Some remarks

• I think the code would be more readable using recursion instead of an explicit stack

• You don't really need visited, you could just change maze fields on the path to 1 temporarily (probably wouldn't do this in "real" code where the maze should be immutable though). Otherwise, I'd just structure it the same way as the maze.

• I'd change push to take a point for symmetry.

• Avoid redundancies bloating the code. For instance, the front == NULL branch in push is redundant with the default case -- the default case will do exactly the same thing in the NULL case.

Edit 2:

If you really want to avoid recursion, I'd change the data structure to this:

typedef struct PathElement {
  int x;
  int y;
  int direction_to_next;
  struct PathElement* next;
  struct PathElement* prev;
} path;

This will allow you to easily go in any direction (for instance, you'll be at the end of a path when you want to print). When you backtrack to a PathElement, increment direction_to_next and continue there until you have exhausted all 4 possible directions. Don't "push" alternatives ahead of time.

Josephjosepha

If I clear the corresponding field in visited when I pop from the stack, then my code will run into an infinite loop. Take for instance 'a' is a parent of 'b'&'c' and c has no further children. So, when 'c' gets pushed after 'a' and the program sees that c has no further way to go, it would pop out 'c' and the front pointer would return to 'a'. Now, if I clear the corresponding visited field of 'c', then 'a' would again go back to c and so on. It would result in an infinite loop. – Laden

This argument does not match your code: b and c are pushed from a before anything else is done and the exploration from b or c should never be able to reach a again because it's marked visited. However, there seems to be a different issue. b and c should be blocked when actually being visited, not when pushed – Josephjosepha

The argument I posed was to your suggestion, not to my code. Nonetheless, I'm getting a better hang of things right now. I'm working upon @Decentralize answer and comments. It would be great if you could contribute over there? I have some doubts there.. – Laden

Using a global visited array is the way to do it when you just want one solution. You want all possible solutions -- so this won't work. You need to prevent cycles another manner -- as I suggested above -- by popping p from the stack and checking if each possible next point q is already in the partial path from start to p. – Decentralize

@Decentralize There is absolutely no problem with a global visited array, just take a look at the working solution attached to the dupe – Josephjosepha

@StefanHaustein nice trick!! :) – Decentralize

Upvoting your answer due to how you explain the resetting the visited array – Decentralize

Answer 2

• For each point in your search, keep a reference to the predecessor point. Always pop the item off your stack after operating on it. Note that if there is no solution, your code will infinite loop. And when you get to the end, you can use the predecessors to backtrack and find the full path.

• Get rid of your visited array, and to prevent cycles during the DFS, check to make sure the point you are adding to the path is not currently in the path. Since you only have 30 possible points in your maze, you could use a bitfield to denote whether the a given point is in the path.

• Also, don't break out of the loop prematurely (upon finding the first available move).

Decentralize

I'm not able to understand you clearly. Reasons being:(i) I think each node in my stack already has a "next" pointer which points to its predecessor. (ii) If I don't break out of a loop prematurely upon the first available move, then how will a decide which "move" to select? In DFS we just select a random move and move on? Moreover, if I backtrack and select the move which hasn't already been exhausted for that node, then I would only get a partial solution right? That's because, I wouldn't get the paths where some nodes are repeating and others aren't. – Laden

It would be great if you could explain me more explicitly and be more ordered and clear. – Laden

Your function is not a proper DFS, which is why you are running into trouble. At a given point in the search, a proper DFS pushes every valid next move onto the stack. Therefore you can't use the stack's next pointer to traverse a potential path. The stack's next pointer is simply to grow the stack. You need to explicitly save a predecessor pointer to backtrack the paths. While stack not empty<br> pop stack<br> check if finished<br> for every next legal move, create new state and push on stack. – Decentralize

Since you want all paths without cycles the "for every next legal move part" needs to check the next candidate point is not in the current path -- either by traversing the predecessor pointers -- or by doing something faster like keeping a bitfield stored in your node struct that denotes the visited points on the partial path. Be warned this function may consume a lot of memory and running time. – Decentralize

Nice! That was quite well explained! I'm getting a better feel of it now. What I have decided now is to add another stack for the "path" - which would consist of the nodes in the path. I would call it a "path-stack" from now on. – Laden

I have a doubt right here. I'll take two eg: (i) lets assume the first path is i-j-k-l(previous nodes have only 1 path, so I'm neglecting that). My path-stack would now contain all the nodes till 'l'. As soon as I encounter 'l', I'll pop out 'l' from my path-stack. The front-pointer would then return to 'k'. Now, a check for the next valid move from 'k' would give me 'o' and 'l'. But, 'l' would again get selected first and the program would run into an infinite loop? How would I prevent 'l' from getting selected again? – Laden

(ii) If however, you tell that I need to look into my "original" stack then I would add o-p-q to my path-stack, the original stack would then contain p-q and this would go on until p-q are emptied and the program would stop! No other way would be added?. – Laden

The part (ii) is what is happening in my above edited program! – Laden

Moreover, in my current program, the visited array would do the same job as checking whether a node has been included in the path. Therefore, I haven't done that part for now. – Laden