Find all the paths in the maze with DFS

Question

Given the source and target cell in the maze, I would like to find all possible solutions for the maze using DFS. 0 is a wall in my maze.

Visualize the maze

I have successfully written a program, but this gives me only one way. I thought about all the possibilities to expand it to all the ways, but, unfortunately, even after an hour (more precisely, 2 days), I could not find a solution.

I was thinking about saving the “visited” array for each node, so when I go back, I am not doing the same move for the previous node. However, the implementation of this will only lead to the creation of a completely different (if any) path, without one node.

I also thought of something else, but even this created some problem.

I also checked similar questions, but none of them are specific to my context. There is a solution using explicit recursion. However, I want to use the stack and find all possible paths. Unfortunately, I could not find anything reliable (at least in such a way that I could understand).

Here is my code for one way.

Edit : I have now implemented the “correct” DFS. I also added a stack to track the current path. Then the program also checks unknown nodes. However, checking it in some other order, and so I can still only get one way!

#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 anyone turn to change this code so that it finds all the ways . Expect community help!

PS: SO currently does not allow me to embed images, and so it automatically created a link.

PS: This question was marked as a duplicate related to some other question. For your information, I asked this question before posting my question! If someone read the answer there, you could see that it was not “accepted”! He just says that you need to do "all" permutations! If one of them would bother to go through a different answer (in another question), they would understand that he applied only to move in the north, northeast or east directions! Moreover, I also made it clear that I do not want a recursive solution - this is what I used another question!

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

Answer 1

I think you need to clear the corresponding field in the visit, where you delete a point from the stack.

Change Another problem is that you need to retreat when you reach the goal. And on your stack, it's probably not clear which unexplored alternatives are and what the current path is (you could use a visited array to track this, but it seems more confusing than just using recursion or adding the appropriate information to your Stack stuct)

In addition, subsequent nodes should be marked visited when they are actually being investigated, and not when they are pushed onto the stack.

Some notes

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

• You really don't need to visit, you could just change the maze fields on the way to 1 temporarily (probably you wouldn’t do this in the "real" code, where the maze should be unchanged, though). Otherwise, I would just structure it like a maze.

• I would modify push to take a point for symmetry.

• Avoid code redundancy. For example, the front == NULL branch in push redundant by default - the default case will do the same in the NULL case.

Edit 2 :

If you really want to avoid recursion, I would 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 example, you will be at the end of the path when you want to print). When you return to PathElement, increase direction_to_next and continue moving until you have exhausted all 4 possible directions. Do not click on "alternatives" ahead of time.

Answer 2

• For each point in your search, keep a link to a predecessor point. Always remove an item from your stack after it has been working. Please note that if there is no solution, your code will be an infinite loop . And when you get to the end, you can use your predecessors to return and find the full path.

• Get rid of your visited array and prevent loops during DFS, make sure that the point you add to this path is not currently located. Since you only have 30 possible points in your maze, you can use the bit field to indicate whether this point is on the way.

• Also, do not exit the cycle prematurely (upon detecting the first available movement).