2009-03-23 - Solution

2009-03-23

This is a weave maze built with a recursive back tracker alogirthm, rendered with a block pattern. I find the weave mazes to be very pretty and slightly more complicated to solve.

2009-03-22 - Solution

Knowing Your Enterance And Exit

When I create a perfect maze (also called a simply-connected maze), I render the whole maze with one of the algorithms I have implemented then I find the entrance and exit with the longest solution path. The way I do this is to move the entrance and exit around the outside of the maze at different locations and "solve" the maze, checking the solution length. When I find the location of the entrance and exit that create the longest solution path I am done creating the maze.

However, finding the entrance and exit to the maze after creating it will not work when creating a braid maze (also called a purely multiply connected maze). With a braid maze there are no dead-ends, which means that all cells in an orthogonal braid maze have at 0, 1, or 2 hedges. The entrance counts as a missing hedge, which means when generating the maze I need to take into consideration the entrance, since that missing hedge on the outside allows the algorithm to add another hedge to that entrance cell. The same with the exit.

Which leaves me with the question, where is the best place to put the entrance and exit in a orthogonal braid maze.

2009-03-22

This site advertises "A Free Daily Online Maze Every Day", however I have been negligent for the last couple of days. Here is a braid maze that I constructed. It is difficult, however I am not particularly proud of it, I would like to construct one with only a single solution path:



Size: 39 x 39
Dead ends: 0
Passages: 1327
Forks: 172
Cross Roads: 20
Decisions: 212
Branches: 99
Corners: 785

Solving - Dead End Filling

Here is a YouTube video of a maze solving technique called dead end filling.

Basically you find all the dead ends and fill them, working backwards down the passages that leads to the dead ends till you reach a junction. If filling the maze leads to a junction that is a dead end you fill that junction and continue backfilling. Keep doing this until all passsages lead to a dead end are filled. What is left (not filled) is the solution path

Braid Mazes - And Their Corners

Braid mazes sometimes called purely multiply connected maze, refers to a maze without any dead ends. In an orthogonal mazes (a maze made up of a square cell with four sided) this means that there are no cells with three sides.

Let's consider the corners of an orthogonal maze. Each corner by default has two sides (unless one of the sides is an exit or and entrance). Which means that the other two sides can not have a wall (hedge) in a braid maze. In other words, the cell in the upper left corner of the maze (Northwest) already has two walls, one to the north and one to the west. Adding a wall on the east or the south would create a dead end.

If we have a orthogonal braid maze without any rooms (vertexes without touching walls) the corners are always passages.

In an orthogonal braid maze where is the best place to put the exit (if this is an outside to outside solution)? If you put the exit in the corners, then you will have one of two scenarios:

1) There will be two solutions paths to the exit, since the corner has to be a passage, both sides of the corner cell could be a path to the solution.

2) There will be one solution path to the corner, and one will be a branch (non-solution path). This is probably the worst scenario of the two, since the solver will never take the non-solution path when they are at the exit. Which means that the branch is wasted space. By wasted I mean, not adding to the complexity of the puzzle.

In conclusion: if you are creating a orthogonal braid maze (no dead ends) and want to have a single solution path without wasted space the exit should not be in a corner.