Please have a look at this link:
Here, the theoretical algorithm given is:
Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell.
But I don't think the animation on it's right uses the same algorithm to generate the maze, though it's not incorrect.
I feel the animation uses this algorithm:
- Start with any unvisited cell, make it a part of the maze and mark it visited.
- Add the unvisited neighbours of that cell to the set of cells that can be considered next
- Choose any one of cells from the set and mark it visited.
- Check if that cell does not have any neighbours that are visited except ONE (the one which caused this cell to be added to the set in the first place). Else go to 3.
- Continue till all cells are visited.
Am I wrong?