Code:
____________
| _________B
| | | | |
| | | | | |_
|___________A
Imagine this is your maze. You start at A, and you want to find the shortest path to B, and also determine if there is a solution. You start by representing the maze as a grid. There are 6 columns and 4 rows, so we'll use a 6x4 matrix.
Code:
-------------------
| | | | | | B|
-------------------
| | | | | | |
-------------------
| | | | | | |
-------------------
| | | | | | A|
-------------------
The value of each cell is some kind of Node structure that you can store information in. In C++ it might look something like this:
Code:
struct Node {
int Shortest = -1; // uninitialized
bool Left = false; // Can we go left from here?
bool Right = false; // Can we go right from here?
bool Up = false; // Can we go up from here?
bool Down = false; // Can we go down from here?
};
when you read it in from the file, you create this matrix and initialize all the Left, Right, Up, and Down values. It might look something like this after you're done initializing.
Code:
-------------------------------
| D R| LR| LR| LR| LR| L| <--finish
-------------------------------
|UD | D R| DL |D | D | |
-------------------------------
|UD |UD |UD |UD |UD | |
-------------------------------
|U L |U LR|U LR|U LR|U LR| L| <--start
-------------------------------
with the Shortest flag set to -1 in every node.
Now you call your recursive function with the node marked start. First thing it does is say "my current path has length 0. The value in this cell says -1. -1 means uninitialied, so I'm just going to write 0 here and proceed.". then it updates Shortest to be 0.
Now, since it's going to proceed, it looks at which moves are possible. It sees that only Left is possible. So it blindly recurses into the left node. Then this process repeats. Let's assume that we always try to expand into adjacent nodes in the order up -> right -> down -> left. Continuing this a few times you can see that it will make the first right and then reach a dead end. What does our grid of shortest path numbers look like at this point? Something like this.
Code:
-------------------
|-1|-1|-1|-1|-1|-1|
-------------------
|-1|-1|-1|-1| 3|-1|
-------------------
|-1|-1|-1|-1| 2|-1|
-------------------
|-1|-1|-1|-1| 1| 0|
-------------------
But we've got nowhere to go, so our function returns. Up to the node with 2, then up to the node with 1. So now it tried U, but there are still L and R left to try. Because of the ordering I specified earlier, it will try right. Note that this is the same direction we came from. Pointless right? But our algorithm doesn't care, it just recurses into it anyway. Now recall what the very step that happened when we began the algorithm was. Quoting exactly, I said earlier "my current path has length 0. The value in this cell says -1. -1 means uninitialied, so I'm just going to write 0 here and proceed." But the valeu in that cell doesn't say -1 anymore, it says 0. And our current path is of length 1 (since that's what we wrote into this cell earlier). So when we add 1 to it, we've now got a length of 2. Indeed, moving left once and then right is two steps. So it compares 2 against 0, finds out that it's greater, so it immediately returns. There is no point revisiting that node.
So now it's back in the cell marked 1. Only 1 direction left to go now, to the left. So it repeats this process again. Let's take a few more steps forward. It goes left, then it goes right and reaches another dead end, then backs up, goes left again, eventually makes it into that loopy area. After it proceeds all the way through that loop, it will look like this:
Code:
-------------------
|-1|-1|-1|-1|-1|-1|
-------------------
|-1| 6| 5| 4| 3|-1|
-------------------
|-1| 7| 4| 3| 2|-1|
-------------------
|-1| 8| 3| 2| 1| 0|
-------------------
Again, it looks to the right to see where to go next, and since 9 is greater than 3, it doesn't even bother. Instead it goes to the left. Eventually it makes it to the end of the maze, and your grid looks like this.
Code:
-------------------
|12|13|14|15|16|17|
-------------------
|11| 6| 5| 4| 3|-1|
-------------------
|10| 7| 4| 3| 2|-1|
-------------------
| 9| 8| 3| 2| 1| 0|
-------------------
So there you go! We're done right? Not quite. The algorithm doesn't even know that's the end. it just knows it can't go any further on that path. As always, it just keeps backing up looking for other paths it hasn't explored. Eventually it gets back to the place where it went Up into that loop area, and realizes it hasn't tried left yet. So it tries left. Now the distance would be 4, but we've already visited that path with a distance of 8. Since 4 < 8, we've found a better path! So it proceeds. It then goes up into that loop area again, once it's no longer the shortest path. Then it backs up, makes a left at the 4, and proceeds to the end. Finally you have this grid.
Code:
-------------------
| 8| 9|10|11|12|13|
-------------------
| 7| 6| 5| 4| 3|-1|
-------------------
| 6| 5| 4| 3| 2|-1|
-------------------
| 5| 4| 3| 2| 1| 0|
-------------------
Now it backs up again, but this time it's tried everything. There's nowhere else to go. Your algorithm completely returns from the recursive call, all the way up to the top. You look at the value stored in the ending square and it says 13. So the shortest path is 13, and it is solvable.
The same analysis works even for an unsolvable maze. Your algorithm will still terminate, but when you look at that cell in the grid, the value will just say -1.