5 5 0 0 4 4 12 10 10 10 9 6 10 9 13 5 14 9 6 1 5 12 2 9 5 5 7 14 2 3 7
The first line represents the dimension of the maze. The second line and third line represents the start coordinates and end coordinates respectively of the maze - the index of the coordinates starts from 0, the first number is the row index and second for the column. The rest represents the maze itself. A cell in a maze is basically a square that has either all or any of the four directions (right, left, top and bottom) closed or open.
In above example, the maze is represented with these numbers:
12 10 10 10 9 6 10 9 13 5 14 9 6 1 5 12 2 9 5 5 7 14 2 3 7
In a simple text based maze, these numbers can be visualized as this:
+-+-+-+-+-+ |S | + +-+-+-+ + | | | | +-+-+ + + + | | | | +-+ +-+ + + | | | | + +-+ + + + | | |E| +-+-+-+-+-+
First, these numbers are just a way to represent the cells of a maze and there are equally many others different ways to do so. Of course, I didn't choose to do it way. In this example, let's look at first cell on this maze which has the number 12 and also observe the corresponding cell in text based maze. We can see that this cell has right and bottom direction open. The numbers are calculated simply using the power of 2 (like binary).
20 = 1
21 = 2
22 = 4
23 = 8
Direction can be visualised like a clock - 3, 6, 9 and 12 in clockwise direction that represents right, bottom, left and top in order to determine the order. So:
Right wall = 1
Bottom wall = 2
Left wall = 4
Top wall = 8
So whenever, we see a wall we add the number. Example, the first cell has only top and left walls. So we add 4+6 to get the number12. Happy? :D. Check and verify that the rest of the numbers represents the corresponding cells on the maze.
I have also provided three different mazes - small, medium and large size ones in the project folder.
C programmers should know how to compile a C program. This is for others. Download gcc for Windows or \*nix according to your OS.~$ gcc -Wall bhuone-maze-solver.c -o bhuone-maze-solverThe arg
-o is the name of the executable file after compiling the program. The name of the file does not matter nor the compiled output.To run the program, simply run the compiled executable with one of the maze inputfile **that must exist** in the path and then filename where the solution to the maze will be written to:
~$ ./bhuone-maze-solver small-maze.txt solution-path.txtMaze simplified! Maze solved!
This create a file solution-path.txt that contains the total number of steps of the solution and then all the direction of the path from start to end like this:
8 RRRRDDDD
If -d flag is provided, it also prints the text version of maze like the one above:
$ ./bhuone-maze-solver small-maze.txt maze-path.txt -d Displaying maze: +-+-+-+-+-+ |S | + +-+-+-+ + | | | | +-+-+ + + + | | | | +-+ +-+ + + | | | | + +-+ + + + | | |E| +-+-+-+-+-+ Maze simplified! Maze solved! Displaying maze after simplifying: +-+-+-+-+-+ |S | +-+-+-+-+ + | | | | | | +-+-+-+-+ + | | | | | | +-+-+-+-+ + | | | | | | +-+-+-+-+ + | | | | |E| +-+-+-+-+-+
However, I do not recommend if the maze is really big like the one I've provided in the project folder. The small and medium mazes should be fine as it does not take too much width space on the terminal.
Example with the medium sized maze:
$ ./bhuone-maze-solver medium_maze.txt maze-path.txt -d Displaying maze: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S | | | | | | | | | | | | +-+-+ + +-+-+-+-+ + +-+ + + +-+ + +-+-+ +-+ + + +-+-+-+ + + +-+ + + + +-+ +-+-+-+ + +-+-+-+ +-+ +-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ + + + +-+ + + +-+-+-+ +-+ + +-+-+ + +-+ + +-+-+-+-+-+ +-+-+ +-+ + + +-+ + + + +-+-+-+-+-+ +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-+ + +-+ +-+-+-+-+ +-+-+-+-+-+ + + +-+ + +-+ + + +-+-+ +-+-+ + +-+-+ +-+ +-+ +-+ +-+-+-+-+ + +-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+ + + + + + + +-+ +-+-+ +-+-+ +-+ + +-+ +-+-+ + + +-+-+ + +-+ +-+-+-+-+ + + + + +-+ + +-+ + +-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+ + + + +-+-+-+-+ + +-+-+-+ + +-+ + +-+-+-+-+ + + + +-+ +-+-+ + + + + + + + + +-+ + +-+ + | | | | | | | | | | | | | | | | | | | | | | | | + + +-+ +-+-+ +-+-+ + +-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+ + +-+-+-+ + + +-+-+-+-+ +-+ + + +-+ + +-+-+ + | | | | | | | | | | | | | | | | | | | | | | + + + +-+ + +-+ + +-+ + + + +-+-+ +-+ + +-+-+-+-+ + + + + +-+-+-+-+ +-+-+-+-+ + + +-+ +-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | + + + + +-+-+ +-+-+-+ + +-+-+ + +-+-+-+ + +-+-+ + + +-+-+-+-+-+-+-+-+ +-+-+ +-+-+-+ +-+ +-+ + +-+-+ + | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+-+ + +-+-+ + +-+-+ + + +-+ + + + +-+ +-+-+-+-+ +-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+ + + + +-+ | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+ + + +-+ + + +-+ + +-+ + +-+ + +-+-+-+ + + +-+ + + + +-+ +-+-+ + +-+-+-+-+-+ +-+-+-+ + +-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + + +-+-+-+ +-+ +-+-+-+ + +-+-+ + +-+ +-+ + +-+-+-+-+-+-+ + +-+ + +-+-+ + + +-+ + + + + +-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+ + + +-+ + + +-+ + +-+-+-+-+-+ +-+ + +-+-+ + + +-+ + + + + +-+ + +-+ +-+ + + +-+-+-+ + +-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+-+ + + +-+-+-+ + + + + + + + +-+ +-+-+ + +-+-+ + +-+ + + +-+ +-+-+ +-+ +-+-+-+-+ + + +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+ +-+ +-+ +-+-+ +-+-+ +-+ + + +-+-+-+ +-+-+ + + + + +-+-+ +-+-+-+ +-+ + +-+ +-+ + +-+ +-+ + +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+ +-+ +-+ + + + + +-+ +-+-+-+-+ + +-+ + + + + + +-+-+ + + +-+ + + +-+-+ +-+ + +-+ +-+ +-+ + + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+-+-+-+ +-+-+ + +-+-+ + +-+ + +-+ +-+-+ + + + +-+-+ + + +-+-+-+-+ + + + +-+-+-+ + +-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ +-+ +-+-+-+-+ + +-+ +-+-+ +-+-+-+ + +-+ + +-+ +-+-+-+-+-+ + + + +-+ + +-+ + +-+ + + + + +-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + + +-+ + +-+-+-+ +-+ + + + +-+ + + +-+-+ + + + + + +-+ +-+-+ + +-+-+ +-+-+ +-+ + +-+ + + +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+ + + + + + +-+ + + + + + +-+-+ + +-+-+ +-+-+ +-+ + + +-+-+-+-+-+-+-+ +-+ + + + +-+ +-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+-+ +-+-+ + +-+-+ + + +-+ +-+ + + +-+ +-+-+ + + +-+-+ + +-+ + +-+-+ +-+ +-+-+-+-+ + + + + +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+ +-+-+ + +-+-+ + +-+ + +-+-+-+-+ + + +-+ + + + +-+ +-+-+ +-+-+-+ + + +-+-+ + + + + +-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+ +-+-+-+ + + + +-+ +-+-+-+ + +-+-+ +-+-+ +-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+ +-+-+ + + + + + | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+ +-+-+ + + + + +-+ + +-+-+-+ +-+ + + + + +-+-+ +-+-+-+ +-+-+ +-+ +-+ +-+-+ +-+ + +-+ + +-+-+ + + | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+ +-+-+-+ + +-+-+-+-+-+-+-+-+ + + + + +-+-+-+ + +-+ + + + +-+-+-+ + + +-+-+-+-+-+-+ + +-+ | | | | | | | | | | | | | | | | | | | | | | | + + + +-+-+ + + +-+ + +-+ +-+-+-+-+ +-+ + + +-+ + +-+ + +-+-+ +-+-+-+-+-+ + + + +-+-+-+-+-+-+ + +-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ +-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+ + + + +-+-+-+-+ + + +-+-+ + + +-+-+ +-+ + + +-+-+ +-+-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+-+ + + + + +-+-+-+-+-+-+-+ +-+-+ +-+ + + +-+-+-+-+-+ + + + +-+ +-+ +-+-+ + + + + + + + + | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ +-+ + +-+-+-+ + +-+ +-+ +-+-+-+ + + +-+-+-+-+-+ +-+ + +-+-+ + +-+ +-+ +-+-+ +-+ +-+ +-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+ + +-+ +-+ + +-+ + + +-+-+-+ +-+-+-+ + + +-+ +-+ +-+-+-+ +-+-+ + + +-+ +-+-+-+-+ + +-+-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | + + + + +-+-+ + + +-+-+-+ + +-+ +-+ +-+-+-+ + +-+ + +-+-+-+-+-+ +-+ +-+-+ + + +-+ + + +-+ + + +-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+-+ +-+-+-+ + + +-+-+ +-+ + + +-+ + +-+ + +-+-+ + + +-+-+ +-+-+ +-+ + + + +-+ + +-+ +-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+-+-+ +-+ + +-+ +-+ + +-+-+ + +-+-+-+ + + + + +-+-+-+ +-+ +-+ + + + +-+ +-+ + +-+ +-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + + +-+ + + +-+ + +-+-+ + +-+-+-+ + +-+-+-+-+-+ + + +-+-+ + +-+-+-+ + +-+ +-+ +-+-+ + + +-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+ +-+ +-+ +-+-+ + + + + + + + +-+-+-+-+-+-+-+ +-+ +-+ +-+-+ + + +-+-+-+ +-+ + +-+ + + +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+ +-+-+-+-+-+ + + +-+-+ +-+-+-+-+ +-+-+-+-+-+ + + +-+ +-+ + +-+-+ + +-+ +-+ +-+ +-+-+ + + +-+ + | | | | | | | | | | | | | | | | | | | | | | | | + +-+ + + + + + +-+-+-+-+-+-+-+ + + +-+-+ + + + + + +-+-+ +-+-+-+-+-+-+ +-+ +-+ +-+-+-+ +-+-+-+ + +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+ + + +-+-+-+-+-+-+ +-+-+ + +-+ + +-+-+-+-+ +-+ + +-+-+-+ + + + +-+ + + + + + + + + +-+ +-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | + + + +-+-+ + +-+ + +-+ + + +-+-+-+ + +-+ + + + +-+ +-+ +-+ + +-+-+-+ + +-+ + +-+-+-+-+-+-+ + + + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+ + + +-+-+ + + + + + +-+-+-+ + +-+-+-+-+ +-+ +-+ +-+ + +-+-+-+ + +-+-+ + + + + + +-+-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+ + +-+-+-+-+ + + + + + + +-+-+-+-+-+-+ +-+ +-+ + +-+ +-+-+ + +-+-+ + +-+-+-+-+-+-+-+-+-+ + + | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+ +-+ + +-+ + +-+-+ + +-+-+ + +-+-+-+-+ +-+ + +-+ +-+-+ +-+-+ + + +-+ + +-+ + +-+-+-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+ +-+ + +-+-+-+-+ + + + + + +-+-+-+ + +-+-+ +-+ + +-+ + +-+ + + + +-+ + + + + + + + + +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+ + +-+-+-+-+-+-+ + + +-+ + + +-+-+-+ + +-+ + +-+ + +-+ + + + + +-+-+-+ + +-+-+ +-+-+-+ + + +-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+ + +-+-+-+-+ + +-+-+-+ + +-+ + + + + +-+ + +-+ + + +-+ + +-+-+-+-+-+-+ + +-+ +-+-+ + + +-+ +-+ + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+ + +-+-+-+-+-+-+-+-+-+-+ + + + + + +-+-+ + + + + + + + +-+-+-+-+ + + +-+ + +-+ + + +-+ +-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+ +-+-+-+ + +-+ +-+-+-+-+-+ + + +-+ + +-+ + + +-+-+-+-+-+ +-+-+ + +-+-+-+-+-+ + +-+-+-+-+-+ + + | | | | | | | | | | | | | | | | | | | + +-+ +-+-+ + +-+-+-+-+ +-+ + + +-+ +-+-+-+ + + +-+ +-+-+-+ + +-+-+-+-+-+-+-+-+-+ +-+-+ + +-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | +-+ +-+-+ +-+-+ +-+-+ + + +-+-+-+ +-+ + + + + +-+ + + +-+-+-+ + + +-+ +-+ + +-+-+-+ +-+-+ + +-+ + + + | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ + + + +-+ +-+ +-+-+-+ + +-+-+-+ +-+-+-+-+-+ +-+-+ + + + +-+-+-+ + +-+ +-+ +-+-+-+-+-+ + +-+ + | | | | | | | | | | E| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Maze simplified! Maze solved! Displaying maze after simplifying: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+ +-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+ + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + +-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ +-+ +-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+ +-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+ + +-+-+ +-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+ +-+-+ +-+ +-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |E| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
With solution file:
172 RRDLLDRDLDDDDDDDDDDRURRRULURURDRURURRRUUURRRRULURRULURURRRRRRDLDDRDLDRRURDRRRRDDLULDDRRRRDRDRDRDDRDDDDDRRRURURDRDRDRUUUURULURRDRDRDDDDDDRDRURDDDRDDDDDDDDDDDLDRDDDDDDDDDDDDD
To get the full idea on each and every steps, please take a look at the source code directly. Also, like any other problems there are multiple different ways of solving it. In this example, I solve the maze by simplifying the maze itself - no specific mathematical formula. I analyze each cell one by one from the start to end and see if any cells are redundant. One easily way to check is to see if the cell has only one opening wall in either right, left or top and bottom. If such cell exists, then it is considered redundant because it's pointless going through that cell only to return back. So soon as I find that cell, I close all the walls of this cell itself. Then I look at the next cell until all the current observable redundant cells are closed. Of course, when we close a cell on each pass, we are actually changing the underlying numbers and this affects all the cells around the changed cell. This means we need to recheck the cells once again from the start and repeat the process again and again until there were no changes to the walls at all. If this successful, then we already have a clear path from the starting point to the end point.
First, this program was never written as a state-of-the-art program. So it does not have any feature to first verify that the file actually represents a proper maze file and in correct format. It is not thoroughly tested and is not the most efficient program in the world because it was never written for efficiency or high performance. It also do not properly support the positional arguments that we normally see in a typical well-written script for specifying the arguments.
On thing that I am really keen on doing (if I get the motivation) is to create a graphical representation of the maze and display the solution path overlayed on it. This might, although, involve porting it into another lang since GUI in C is not my cup of tea.