labyrinth(it's dubbed as numeric maze matrix-backtracking)

**~~RyanC~~** · 05-01-2015

Well, the title seemed weird but the content isn't totally meaning the direct concept of labyrinth, it's in abbreviation words, a maze consisted of matrix that in every byte there's either 0 or 1, that 0 resemble a wall, and 1 is meaning 'you can move', it has a particular entrance and exit which they are 'the first byte in the upper left hand corner of the matrix(entrance..,first byte in the matrix), the last byte in the corner in the down-right of the matrix(exit,last byte in the matrix mat[n][n])'.
Moreover, the maze has too many paths inside it to get out from the exit, which the player can only move in two directions: up and down, and must find all the paths, print all of them as output row by row on the screen.
if there's no paths must clear out on the screen that the maze isn't solved!!
(you can see the photo that are attached in, for instance what is marked in the red is one of the paths that led the player gets out of the maze..there's maybe more than path..)

-I've been struggling about six hours to write a code that printing and gives all the possible paths by a recursive way and just by(by others method would be a lil easy like a loop ..etc), unfortunately I didn't succeed, I tried much and much, but just getting bugs in my code, So I'm stuck and don't know how to compile it properly

, I need someone to write a code for this problem for just knowing how the things go in maze problems!!
.
the code that I was trying in: (after editing it many times and removing/adding..etc)

Code:

#include <stdio.h>
    
// Don't need to keep direction for this one, although it does need a global array.
 
// This array holds a 1 if the corresponding square in the
//  maze is blocked, and a 1 if the square is allowed to be
//  has a 0 in it for every square with a wall.
int blocked [X_SIZE][Y_SIZE] = {};
 
int TraverseMaze (int x, int y)
{
 // If you're on an illegal square, you fail.
 if (blocked[x][y]) return 0;
 
 // Block the current square.  No moves after this may use this
 //  square.
 blocked[x][y] = 0;
 
 // Try this function on each of the 4 directions. 
 if (TraverseMaze (x + 1, y)) return 1;
 if (TraverseMaze (x - 1, y)) return 1;
 if (TraverseMaze (x, y - 1)) return 1;
 if (TraverseMaze (x, y + 1)) return 1;
 
 // If all 4 directions fail, then throw in the towel.
 blocked[x][y] = 0;
 return 0;
}
traverseMaze( int x, int y )
{
    maze[x][y]++; /* mark square as used */
    if( !maze[x][y-1] ) traverseMaze( x, y-1 );
    if( !maze[x+1][y] ) traverseMaze( x+1, y );
    if( !maze[x][y+1] ) traverseMaze( x, y+1 );
    if( !maze[x-1][y] ) traverseMaze( x-1, y );
}

I really need a help,I'm new in C programming, but still believe that I can and overcome on that problem, btw, I know the idea of behind what the code would do, but scripting it in the code is hard for me, So would be nice and appreciated much if anyone can help me and by explaining, writing a code for solving this problem please!!

thanks beforehand!.

**Salem** · 05-01-2015

> // Don't need to keep direction for this one, although it does need a global array.
Stop making excuses for bad habits.

> // Block the current square. No moves after this may use this
> // square.
> blocked[x][y] = 0;
This isn't what your earlier comment said.

Start with
#define OPEN 0
#define BLOCKED 1

Then you might end up with more readable code like
if ( blocked[x][y] == BLOCKED ) return BLOCKED;

And post a complete effort, not some random sections of code that won't compile.

> I know the idea of behind what the code would do, but scripting it in the code is hard for me
Yes it is, but you have to struggle by yourself if you ever want to be a programmer. Developing the skill that allows you to 'see' the path from the requirements (text, pictures etc) to actual lines of code is a must.

So no, we won't be just giving you the code to look at.

**Nominal Animal** · 05-02-2015

There is a simple way to solve any maze, by finding out the number of steps needed to reach the closest exit (or entrance).

To do this, you need to have an array (a matrix) of unsigned integers. The largest number we'll ever store in it is the total number of reachable points in the matrix; for simplicity, you can use the size of the matrix. (Note that we also need zero, so there are rows×cols+1 integer values we might wish to use.)

Set all unreachable points (walls and such) to zero, all reachable points to that largest number. Mark all entries, or all exits, by 1. (Do not mark both! Clever routines work faster if you mark those that you have fewer of.)

Wherever you have two nonconsecutive positive numbers next to each other, you set the larger one to smaller one + 1, because the larger ones position is shorter to reach via that smaller one, and these two positions are next to each other. This is repeated as long as such conditions occur in the maze. You end up with each reachable position marked with the shortest number of steps needed, to reach the closest point you originally marked with 1.

A naive brute force loop ends up being O(rows² cols²), i.e. O(N⁴). It's fast for small matrices, but gets really, really slow, as the matrix size grows. Noticing that the changes are localized to the four nearest neighbours wherever you modify a point will lead to much faster approaches. It turns out to be pretty similar to generating mazes in the first place.

You can compare the steps needed to reach the other end by just examining the numbers stored in those points. They denote the number of steps needed to reach the nearest 1, and the path will be achieved by following consecutive integers.

However, all the dead ends are still listed in the matrix.

You can prune out the dead ends. Wherever you have a step value above 1 and less than the number of steps to the selected entrance/exit, and that step value is also larger than its four neighboring values (only considering those that have step values between 1 and the number of steps to the selected entrance/exit), it means that point is a dead end. You discard those by changing its step value to the largest possible number, meaning it is a possible position, but not on the shortest path. And you'll need to re-examine the four nearest neighbours to find out if they became dead end.

When there are no longer any such step values, you end up with a matrix that has the optimum path marked (in sequence) from 1 to the number of steps to the selected entrance/exit, and all unused but valid points set to the largest possible number.

If each positive integer less than the largest possible number occurs only once in the matrix, you have a unique solution. Otherwise, there are equally short alternate segments in the path.

If you need an unique path, pick one of the duplicate values (at random), and set it to the largest possible number, and repeat pruning the dead ends. Then, if there are still duplicate values, you repeat this entire step, including the pruning part.

I know this works, because I've implemented it. It's pretty fun, too, and I didn't see any nasty gotchas that might bite new programmers in it. It looks like a good learning opportunity to me.

**~~RyanC~~** · 05-02-2015

Originally Posted by Salem

> // Don't need to keep direction for this one, although it does need a global array.
Stop making excuses for bad habits.

> // Block the current square. No moves after this may use this
> // square.
> blocked[x][y] = 0;
This isn't what your earlier comment said.

Start with
#define OPEN 0
#define BLOCKED 1

Then you might end up with more readable code like
if ( blocked[x][y] == BLOCKED ) return BLOCKED;

And post a complete effort, not some random sections of code that won't compile.

> I know the idea of behind what the code would do, but scripting it in the code is hard for me
Yes it is, but you have to struggle by yourself if you ever want to be a programmer. Developing the skill that allows you to 'see' the path from the requirements (text, pictures etc) to actual lines of code is a must.

So no, we won't be just giving you the code to look at.

Sorry brah, if you are thinking that I'm going to copy paste the code, you would be wrong and it's even illegal in the forum, I've been trying and trying but no offence so what would I do?(as a new programmer) if you were instead of me, you would exactly figure out this situation.

I've scripted a code for solving it and its succeeded, but not in a recursive way, in contrary of all what I needed is (in a recursive).

Also you can see my last comment over here and would figure out my trying of, thanks for your cooperation anyway.

**~~RyanC~~** · 05-02-2015

Originally Posted by Nominal Animal

There is a simple way to solve any maze, by finding out the number of steps needed to reach the closest exit (or entrance).

To do this, you need to have an array (a matrix) of unsigned integers. The largest number we'll ever store in it is the total number of reachable points in the matrix; for simplicity, you can use the size of the matrix. (Note that we also need zero, so there are rows×cols+1 integer values we might wish to use.)

Set all unreachable points (walls and such) to zero, all reachable points to that largest number. Mark all entries, or all exits, by 1. (Do not mark both! Clever routines work faster if you mark those that you have fewer of.)

Wherever you have two nonconsecutive positive numbers next to each other, you set the larger one to smaller one + 1, because the larger ones position is shorter to reach via that smaller one, and these two positions are next to each other. This is repeated as long as such conditions occur in the maze. You end up with each reachable position marked with the shortest number of steps needed, to reach the closest point you originally marked with 1.

A naive brute force loop ends up being O(rows² cols²), i.e. O(N⁴). It's fast for small matrices, but gets really, really slow, as the matrix size grows. Noticing that the changes are localized to the four nearest neighbours wherever you modify a point will lead to much faster approaches. It turns out to be pretty similar to generating mazes in the first place.

You can compare the steps needed to reach the other end by just examining the numbers stored in those points. They denote the number of steps needed to reach the nearest 1, and the path will be achieved by following consecutive integers.

However, all the dead ends are still listed in the matrix.

You can prune out the dead ends. Wherever you have a step value above 1 and less than the number of steps to the selected entrance/exit, and that step value is also larger than its four neighboring values (only considering those that have step values between 1 and the number of steps to the selected entrance/exit), it means that point is a dead end. You discard those by changing its step value to the largest possible number, meaning it is a possible position, but not on the shortest path. And you'll need to re-examine the four nearest neighbours to find out if they became dead end.

When there are no longer any such step values, you end up with a matrix that has the optimum path marked (in sequence) from 1 to the number of steps to the selected entrance/exit, and all unused but valid points set to the largest possible number.

If each positive integer less than the largest possible number occurs only once in the matrix, you have a unique solution. Otherwise, there are equally short alternate segments in the path.

If you need an unique path, pick one of the duplicate values (at random), and set it to the largest possible number, and repeat pruning the dead ends. Then, if there are still duplicate values, you repeat this entire step, including the pruning part.

I know this works, because I've implemented it. It's pretty fun, too, and I didn't see any nasty gotchas that might bite new programmers in it. It looks like a good learning opportunity to me.

Im with you, it's a good opportunity for new programmers, and its look like really a new amazing step for progress your skills, and the idea of what you're trying to explain is already found for me (hard to script it on codes), I really tried hard for solving the question/problem in a recursive way!! have been about 8 hours or abit more!!, and if I would complete then offence for, just wasting the time!!., to be more frankly succeeded in scripting a code for solving the problem but in a loop way and others method, for me still not solving my problem because I need it in a recursive way, anyone can help me and here write a code by recur? I truly not going to copy and paste it as a dumb, I want to know how its going and even the idea behind of what's going in whole the maze issues.

if you or anyone can post a code of what you're telling, then would be nice and much appreciated!!

thanks in advance for every cooperation.

**~~RyanC~~** · 05-02-2015

Well, I have followed step by step the content of Nominal Animal 's explanation and I have arrived to this code after struggling by a recursive way!!

Code:

 
#define n 10
#define UP 1
#define DOWN -1
#define RIGHT 2
#define LEFT -2
 
// Mazes Solver Function //
// "i" resembles a rows, "j" resembles a columns//
int solve (int board[n][n], int i, int j, int direction)
{
    int m;
    if (i+j == n*2-2)
       return 1; 
    m=0;
    if ((i+1 >= n || !board[i+1][j]))
     m++;
    if (!board[i][j+1] || j == n-1)
     m++;
    if (!board[i-1][j] || i == 0)
     m++;
    if (!board[i][j-1] || i == 0)
     m++;
    if (m > 2)
     board[i][j] = 0;
    if (board[i+1][j] && i<n-1 && (direction*(-1) != UP || !board[i][j]))
     return solve (board, i+1, j, DOWN);
    else if (board[i][j+1] && j<n-1 && (direction*(-1) != RIGHT || !board[i][j]))
     return solve (board, i, j+1, RIGHT);
    else if (board[i-1][j] && i>0 && (direction*(-1) != DOWN || !board[i][j]))
     return solve (board, i-1, j, UP);
    else if (board[i][j-1] && j>0 && (direction*(-1) != LEFT || !board[i][j]))
     return solve (board, i, j-1, LEFT);
    else return 0;
}

it's unfortunately not compiling for me and appearing that there's a bug which is "fatal error LNK1120: 1 unresolved externals", its the first time as a new programmer facing this kind of errors.

anyone can help me to figure out what is the wrong with my code for solving and let it compiles?

thanks.

**~~RyanC~~** · 05-02-2015

I've edited it and used others libraries but still the same error so kept it as it was previously(the same code I've posted above), I'm obviously I'm missing something that is probably obvious more for real programmers, but its what?

any assistance please!!

**Nominal Animal** · 05-02-2015

Originally Posted by RyanC

solving the question/problem in a recursive way

Why? The recursion may end up being quite deep, and because of practical stack size limitations, the approach may limit you to very small mazes. Your example maze is only 7×7, giving a the maximum recursion depth is 49, which is still safe.

When writing recursive functions, you really should print the state at each recursive call, to see exactly the changes each function does.

I wrote a 222-line example program to find out if there are any potholes in the recursive solution. Here is what my program outputs for me:

Code:

  1  0  0  0  0  0  0   1. check() call.
 64  0  0 64 64 64  0
 64  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   2. check() call, called by 1.
  2  0  0 64 64 64  0
 64  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   3. check() call, called by 2.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   4. check() call, called by 2.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   5. check() call, called by 4.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   6. check() call, called by 4.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   7. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   8. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   9. check() call, called by 8.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   10. check() call, called by 8.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   11. check() call, called by 10.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   12. check() call, called by 10.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   13. check() call, called by 12.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   14. check() call, called by 12.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   15. check() call, called by 14.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   16. check() call, called by 14.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   17. check() call, called by 16.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   18. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   19. check() call, called by 18.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   20. check() call, called by 18.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   21. check() call, called by 20.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   22. check() call, called by 21.
  2  0  0 64 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   23. check() call, called by 22.
  2  0  0  9 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   24. check() call, called by 22.
  2  0  0  9 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   25. check() call, called by 24.
  2  0  0  9 10 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   26. check() call, called by 24.
  2  0  0  9 10 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   27. check() call, called by 26.
  2  0  0  9 10 11  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   28. check() call, called by 26.
  2  0  0  9 10 11  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   29. check() call, called by 28.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   30. check() call, called by 28.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   31. check() call, called by 30.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   32. check() call, called by 30.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   33. check() call, called by 32.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   34. check() call, called by 32.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   35. check() call, called by 34.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   36. check() call, called by 34.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   37. check() call, called by 36.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 16 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   38. check() call, called by 37.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   39. check() call, called by 38.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   40. check() call, called by 38.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   41. check() call, called by 40.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   42. check() call, called by 40.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   43. check() call, called by 42.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   44. check() call, called by 42.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   45. check() call, called by 44.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   46. check() call, called by 44.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   47. check() call, called by 46.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   48. check() call, called by 46.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   49. check() call, called by 48.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   50. check() call, called by 37.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   51. check() call, called by 36.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   52. check() call, called by 21.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   53. check() call, called by 20.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. trim() call.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. trim() pass.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. prune() call.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 -1  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   2. prune() call, called by 1.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   3. prune() call, called by 2.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   4. prune() call, called by 3.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   5. prune() call, called by 4.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0 -1  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   2. trim() pass.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0 -1  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

Maximum recursion depth was 23 calls.

 * 0 0 0 0 0 0
 * 0 0 * * * 0
 * 0 0 * 0 * 0
 * * * * 0 * 0
 0 1 0 0 0 * 0
 0 1 0 * * * 0
 0 1 0 * 0 0 0
 1 1 0 * * * *
 0 0 0 0 0 0 *

Since you said that start and end point must start vertically, I added one extra row for the start and the exit. I didn't need "direction", only the maze and the row and column in it to examine. prune() also needed the exit location, so it wouldn't remove that; otherwise the exits look exactly like dead ends.

The check() function is the recursive function that checks if the current cell has a step distance that can be reduced (by checking the four neighbours). It is initially called to check the leftmost column in the second row, after the starting point at the top left corner is assigned 1, and all other valid places N=7×9+1=64.

After a total of 53 check() calls, having maximum recursion depth of 23 calls, we have the minimum number of steps needed to reach the exit, assigned to each valid place in the maze.

The trim() call scans through the array, until it finds a dead end (a point that is not an exit, but is further from the exit than any of its neighbours). As a dead end, I remove it by assigning it a distance of -1, and calling prune() on all four neighbours (if they're valid places too, not -1, not exit) to see if any of them now became a dead end.
It is called only once, but it repeats the maze scan until no dead ends are found.

Using signed integers turned out to be nice, as "walls" are zero, and dead ends are similarly uninteresting; putting dead end paths at -1 means everything interesting is positive.

Also, at the beginning of trim() it does a pass over the entire array, setting all points further than the exit to -1, because they obviously have to be dead ends. This is an optimization, I believe, and in this particular maze it does not matter, as it only shows up when you have a short path from start to exit, and longer dead end paths.

The prune() function is also recursive. It checks if the specified position in the maze is a dead end, and if so, it is removed by assigning it a distance of -1, and recurses into the four neighbours (if they're valid places too, not -1, not exit), to see if any of them now became a dead end.

The only issue I had when writing the function, was to remember to check that I don't remove the exits. It was obvious, as the trim() removed the exit on the first pass, and then erased the entire path, leaving me with just 0 and -1 entries.

**~~RyanC~~** · 05-02-2015

Originally Posted by Nominal Animal

Why? The recursion may end up being quite deep, and because of practical stack size limitations, the approach may limit you to very small mazes. Your example maze is only 7×7, giving a the maximum recursion depth is 49, which is still safe.

When writing recursive functions, you really should print the state at each recursive call, to see exactly the changes each function does.

I wrote a 222-line example program to find out if there are any potholes in the recursive solution. Here is what my program outputs for me:

Code:

  1  0  0  0  0  0  0   1. check() call.
 64  0  0 64 64 64  0
 64  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   2. check() call, called by 1.
  2  0  0 64 64 64  0
 64  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   3. check() call, called by 2.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   4. check() call, called by 2.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
 64 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   5. check() call, called by 4.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   6. check() call, called by 4.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4 64 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   7. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   8. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0 64  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   9. check() call, called by 8.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   10. check() call, called by 8.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0 64  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   11. check() call, called by 10.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   12. check() call, called by 10.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0 64  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   13. check() call, called by 12.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   14. check() call, called by 12.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64 64  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   15. check() call, called by 14.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   16. check() call, called by 14.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 64  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   17. check() call, called by 16.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   18. check() call, called by 6.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5 64 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   19. check() call, called by 18.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   20. check() call, called by 18.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6 64  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   21. check() call, called by 20.
  2  0  0 64 64 64  0
  3  0  0 64  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   22. check() call, called by 21.
  2  0  0 64 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   23. check() call, called by 22.
  2  0  0  9 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   24. check() call, called by 22.
  2  0  0  9 64 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   25. check() call, called by 24.
  2  0  0  9 10 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   26. check() call, called by 24.
  2  0  0  9 10 64  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   27. check() call, called by 26.
  2  0  0  9 10 11  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   28. check() call, called by 26.
  2  0  0  9 10 11  0
  3  0  0  8  0 64  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   29. check() call, called by 28.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   30. check() call, called by 28.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 64  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   31. check() call, called by 30.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   32. check() call, called by 30.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 64  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   33. check() call, called by 32.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   34. check() call, called by 32.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 64  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   35. check() call, called by 34.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   36. check() call, called by 34.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 64 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   37. check() call, called by 36.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 64 16 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   38. check() call, called by 37.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 64  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   39. check() call, called by 38.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   40. check() call, called by 38.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 64 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   41. check() call, called by 40.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   42. check() call, called by 40.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 64 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   43. check() call, called by 42.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   44. check() call, called by 42.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 64 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   45. check() call, called by 44.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   46. check() call, called by 44.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 64
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   47. check() call, called by 46.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   48. check() call, called by 46.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 64

  1  0  0  0  0  0  0   49. check() call, called by 48.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   50. check() call, called by 37.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   51. check() call, called by 36.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   52. check() call, called by 21.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   53. check() call, called by 20.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. trim() call.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. trim() pass.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 10  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   1. prune() call.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 -1  9  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   2. prune() call, called by 1.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0  8  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   3. prune() call, called by 2.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0  7  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   4. prune() call, called by 3.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0  6  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   5. prune() call, called by 4.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0 -1  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

  1  0  0  0  0  0  0   2. trim() pass.
  2  0  0  9 10 11  0
  3  0  0  8  0 12  0
  4  5  6  7  0 13  0
  0 -1  0  0  0 14  0
  0 -1  0 17 16 15  0
  0 -1  0 18  0  0  0
 -1 -1  0 19 20 21 22
  0  0  0  0  0  0 23

Maximum recursion depth was 23 calls.

 * 0 0 0 0 0 0
 * 0 0 * * * 0
 * 0 0 * 0 * 0
 * * * * 0 * 0
 0 1 0 0 0 * 0
 0 1 0 * * * 0
 0 1 0 * 0 0 0
 1 1 0 * * * *
 0 0 0 0 0 0 *

Since you said that start and end point must start vertically, I added one extra row for the start and the exit. I didn't need "direction", only the maze and the row and column in it to examine. prune() also needed the exit location, so it wouldn't remove that; otherwise the exits look exactly like dead ends.

The check() function is the recursive function that checks if the current cell has a step distance that can be reduced (by checking the four neighbours). It is initially called to check the leftmost column in the second row, after the starting point at the top left corner is assigned 1, and all other valid places N=7×9+1=64.

After a total of 53 check() calls, having maximum recursion depth of 23 calls, we have the minimum number of steps needed to reach the exit, assigned to each valid place in the maze.

The trim() call scans through the array, until it finds a dead end (a point that is not an exit, but is further from the exit than any of its neighbours). As a dead end, I remove it by assigning it a distance of -1, and calling prune() on all four neighbours (if they're valid places too, not -1, not exit) to see if any of them now became a dead end.
It is called only once, but it repeats the maze scan until no dead ends are found.

Using signed integers turned out to be nice, as "walls" are zero, and dead ends are similarly uninteresting; putting dead end paths at -1 means everything interesting is positive.

Also, at the beginning of trim() it does a pass over the entire array, setting all points further than the exit to -1, because they obviously have to be dead ends. This is an optimization, I believe, and in this particular maze it does not matter, as it only shows up when you have a short path from start to exit, and longer dead end paths.

The prune() function is also recursive. It checks if the specified position in the maze is a dead end, and if so, it is removed by assigning it a distance of -1, and recurses into the four neighbours (if they're valid places too, not -1, not exit), to see if any of them now became a dead end.

The only issue I had when writing the function, was to remember to check that I don't remove the exits. It was obvious, as the trim() removed the exit on the first pass, and then erased the entire path, leaving me with just 0 and -1 entries.

Why?
because I already solved it by others methods like loops and struct..bla bla, but I'm willing for solving it by a recursive way as I see it as a semi-challenge for the new programmers, I still am misunderstanding you and your code's output a lil weird for me (as a new programmer, some of your function is about strange for me) but I understand the plot of what you're willing to throw out of your speech, I really found it hard and just wasting time and time, may you post your code for? just want to get the idea and the logic of how the things go in! , I already made a code-posted it above- but still there's error above.

by the way, the matrix can be any input matrix, doesn't matter what its size is, which must be NxN (square).

would be appreciated if anyone can post a description script of a code of finding paths following my problem's orders.

thanks!!!

**Nominal Animal** · 05-03-2015

Originally Posted by RyanC

may you post your code

I thought about it long and hard ... and the computer says no.

I ascribe to the "If you give a man a match, he'll be warm for a minute, but if you light them on fire, they'll be warm for the rest of their life" viewpoint.

In other words, that reading others' answers without finding your own, is worthless; a fool's errand. You may think you learn enough that way, but truth is, you only get a superficial feel for it, unless you learn how to find the answer yourself.

Your approach to learning seems to be that you prefer to learn answers and patterns of answers by rote, instead of trying to find understanding. I don't like that, and I'm not interested in helping you along that approach.

Understanding requires personal effort. I help only those who show such effort.

**~~RyanC~~** · 05-03-2015

Originally Posted by Nominal Animal

I thought about it long and hard ... and the computer says no.

I ascribe to the "If you give a man a match, he'll be warm for a minute, but if you light them on fire, they'll be warm for the rest of their life" viewpoint.

In other words, that reading others' answers without finding your own, is worthless; a fool's errand. You may think you learn enough that way, but truth is, you only get a superficial feel for it, unless you learn how to find the answer yourself.

Your approach to learning seems to be that you prefer to learn answers and patterns of answers by rote, instead of trying to find understanding. I don't like that, and I'm not interested in helping you along that approach.

Understanding requires personal effort. I help only those who show such effort.

Your approach of analyzing isn't correct, but the proverb in this case on its point, I should try and try more than one.

thank, and appreciate your attitude.

**Nominal Animal** · 05-03-2015

To prove that I really have taken a long, deep think on this.

Please try your implementations on the following maze.

Code:

↓
1 1 1 1 1 1 1
0 0 0 0 0 0 1
1 1 1 1 0 0 1
1 0 0 1 0 0 1
1 0 0 1 0 0 1
1 0 0 1 0 0 1
1 1 1 1 1 1 1
            ↓

A plain backtracking algorithm cannot exclude the cycle on the lower left corner, because it does not find any dead ends.

blocked element

0 in the matrix

open element

1 in the matrix

entrance, exit

starting and ending elements

dead element

a formerly open element that was not in the direct path from an entrance to an exit

dead end

An open element with at most one open element neighbour. Entrances and exits are never dead ends, even if they only have one open element neighbour.

neighbour

Adjacent elements, i.e. left, right, above, or below. Diagonally adjacent elements are not neighbours.

pruning, dead end backtracking

When an open element turns into a dead element, some or all of its open element neighbours may become dead ends, so they need to be checked and turned into dead elements too. Because there may be at most only one open neighbour per dead element, this can be done in a simple loop; there is no need for recursion.

To find the optimum path, and to remove cycles like in the above matrix, one should replace the open elements with their step distance to the nearest exit:

Code:

↓
13 12 11 10 9  8  7
0  0  0  0  0  0  6
11 10 9  8  0  0  5
10 0  0  7  0  0  4
9  0  0  6  0  0  3
8  0  0  5  0  0  2
7  6  5  4  3  2  1
                  ↓

Edited: If there is only one exit, the distance to it can be calculated using a single pass over the matrix, as long as the pass is done in nondecreasing order of rectilinear distance to that exit. Oops, make that nondecreasing order of step distance, of course. Backtracking is actually needed. The step distance from any cell is one plus the minimum step distance of any neighbour. Changing the step distance of an element may change the step distance for up to three neighbours (because the fourth must have been the one that was already closer than that element).

Think of the distance as a tidal wave, starting from each exit. It is closest at 1 at the exit, and grows weaker (increases by one) step by step, as it traces the open elements in order of increasing step distance.

step distance

The number of steps needed to reach an exit

rectilinear distance

L₁ distance, or Manhattan distance, or taxicab distance. Mathematically, ∑|a_i-b_i|, where index i is over dimensions, and a_i and b_i are coordinates. Here, rectilinear distance = (difference in rows) + (difference in columns).

Edited: If there is only one exit at the lower right corner, all elements on the same ascending diagonal (from lower left to upper right) are at the same rectilinear distance to the exit. Therefore, you only need a single pass over the maze: an outer loop to cover all ascending diagonals, and an inner loop to handle the elements on each diagonal. In the inner loop, you only need to check the element on the right, and the element below. Nope, I was wrong. See above edit.

Edited: Note: The step distance matches the rectilinear distance only for simple mazes. When there are hooks and bends in the path, the step distance is greater. The step distance can never be less than the rectilinear distance to the same exit.

To eliminate non-optimum path (those that are not along the shortest paths from an entrance to an exit), you do pruning, but with an additional twist:

an initial dead end

An element further away from an exit than any of its neighbours. Entrances are not initial dead ends.

This time, an element may have two, three, or even four open neighbours, and still be initial dead ends. All open neighbours to an initial dead end, excluding entrances and exits, are dead ends as described earlier.

A single pass over the matrix will correctly locate initial dead ends. If you mark each one dead, you can prune those neighbors that became dead ends.

This step is at most O(N²) time complexity, because you can have a fraction of N initial dead ends, and each prune has linear time complexity (can be a fraction of N long). (I think there might be a mathematical trick to prove that this actually is O(N), because we only consider initially open elements, and turn them dead.)

Even if you had many entrances and exits, you could just create a helper matrix that contains the rectilinear distances to the nearest exit, and sort it (along with a reference to the matrix element), so you can easily scan the matrix in nondecreasing order of rectilinear distance to the nearest exit. The sort is O(N log N), N being the number of open elements in the matrix.

If there are closed cycles so that the optimal solution is not unique -- it has partial forks or loops that result in equally short solutions --, you can trivially pick one in a linear pass by starting from any entrance, and picking any neighbour with a smaller step distance. In the fork points, there are more than one, but each one is guaranteed to reach the exit in the same number of steps, so you can pick between them at random, or using any rule you want (say, first one you notice).

When I first posted to this thread, I didn't know all of the above. I do, now, and I can prove it, too. And I'm continuing to learn new details about this, the more I think about it.

What have you learned?

Thread: labyrinth(it's dubbed as numeric maze matrix-backtracking)

Thread Tools

Search Thread

Display

labyrinth(it's dubbed as numeric maze matrix-backtracking)

Similar Threads

alpha-numeric to numeric program

Labyrinth generation

Need Help: Storing numeric data into matrix from a data file

about the backtracking method and maze

Maze game, complete with maze editor and an example maze!