Need help visualizing maze-solving algorithm

[usinjin]

Hello,

I'm fairly new to C++ programming, and I'm working on a maze solving algorithm. I need to use a stack to keep track of the moves of done, so no recursion.

Basically I'm responsible for the "Solver" algorithm, I can check to see if a move is available or blocked and do it, or I can undo a move. The moves are left, right and forward. There is already code that takes care of drawing and updating the maze.

What I could use is just some help understanding the basic algorithm for traversing the maze. I've looked at a lot of different programs for doing it, but I just can't seem to figure it out. The maze I'm solving is generated randomly, with no loops.

Here is what I can't wrap my mind around: say I have a straight section of wall, but there's a branch coming out of the wall as well. Say I decide to go down this other branch, but eventually it leads to a dead end. I've pushed all the moves I've done onto the stack. Basically, how do I know how many moves I need to pop off the stack to know I'm back at the original junction, so I can take the other branch instead of the blocked one?

Thanks for any help!