Find all the possible paths through the maze

Question

I am trying to create a program that will go through a randomly created labyrinth, where 1 is open and 0 is walls. starting from the upper left corner and ending in the lower right corner. The path can go up, down, left and right.

My program currently gives me a solution, but it's hard for me to get it to print several paths.

I read several different versions of this problem, but I can not find it with my parameters.

Here is my code, I have omitted the part where I randomly create my maze.

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <stdbool.h> int n, minMatrix, solIndex = 1, minLen = 10000000; //I use the latter 3 variables in order to find the shortest path, not relevant for now bool solveMaze(int mat[n][n],int x, int y, int sol[][n], int count){ int i, j; if((!(x >= 0 && x <n && y >=0 && y < n)) || mat[x][y] == 0 || sol[x][y] == 1){ return false; } if(x == n-1 && y == n-1){ sol[x][y] = 1; printf("Solution %d is:\n", solIndex); for(i = 0; i < n; i++) { for( j=0;j<n;j++) { printf("%d", sol[i][j]); } printf("\n"); } if(count<minLen) { minLen = count; minMatrix = solIndex; } solIndex +=1; sol[x][y] = 0; return true; } sol[x][y] = 1; if(solveMaze(mat, x+1, y, sol, count+1)){ return true; } if(solveMaze(mat, x-1, y, sol, count+1)){ return true; } if(solveMaze(mat, x, y+1, sol, count+1)){ return true; } if(solveMaze(mat, x, y-1, sol, count+1)){ return true; } sol[x][y] = 0; return false; } 

I missed the part of my core where I randomly create my maze.

 int main(){ if(!solveMaze(**mat, 0, 0, sol, 0)){ printf("No possible paths, run program again\n"); } else{ printf("the shortest path is %d\n", minMatrix); } } 

For example, if I have a maze

 1100111111 1101111111 1111110110 1110011111 1101101011 1111101011 1110111101 1100111111 1110111011 1101101111 

He gives me the first path he finds

 1000000000 1001100000 1111110000 1100011000 1100001000 1100001000 1100001000 1100001011 1100001011 1100001111 

Although this requires a roundabout, because of the preferences to go in the order of down, up, right and left, this is another way.

So, ultimately, I'm not sure how to iterate over multiple paths.

Answer 1

I finally found a solution to your question. but honestly, this is not a solution that I developed, some other people (namely: Schröder) had this idea before!

the problem is described by Schröder , but look at the German translation for a binary tree permutation.

convert your path and all available nodes to a binary tree and rearrange it! (but be careful, there may be many solutions)

as you can see, these are all solutions for crossing a 4x4 square (the mirror part is missing, but alas).

Answer 2

A simple, fully working solution, using the labyrinth example from this similar question (which was marked as a duplicate but was autonomous compiled): Find all the paths in the labyrinth using DFS

It uses simple DFS with direct recursion, which looks the same as here. It tracks the current track in a single copy of the line and changes the maze in place to block the current track.

 #include <iostream> #include <string> const int WIDTH = 6; const int HEIGHT = 5; void check(int x, int y, int dest_x, int dest_y, int (&maze)[HEIGHT][WIDTH], std::string& path) { if (x < 0 || y < 0 || x >= WIDTH|| y >= HEIGHT || !maze[y][x]) { return; } int len = path.size(); path += (char) ('0' + x); path += ','; path += (char) ('0' + y); if (x == dest_x && y == dest_y) { std::cout << path << "\n"; } else { path += " > "; maze[y][x] = 0; check (x + 0, y - 1, dest_x, dest_y, maze, path); check (x + 0, y + 1, dest_x, dest_y, maze, path); check (x - 1, y + 0, dest_x, dest_y, maze, path); check (x + 1, y + 0, dest_x, dest_y, maze, path); maze[y][x] = 1; } path.resize(len); } int main() { int maze[HEIGHT][WIDTH] = { {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}}; std::string path; check(0, 0, 4, 3, maze, path); return 0; } 

Runnable version: https://code.sololearn.com/cYn18c5p7609