Copyright ©, 2008–2009

Go to for downloading the latest release.


:: Screen Saver
:: The Maze
   :: Images
   :: Irregular Mazes
   :: Outline Shapes
   :: Embedded Mazes
:: Solver Strategies
   :: Efficient Solvers
   :: Heuristic Solvers
   :: Extreme Strategies
   :: Observations
:: Summary
:: Package Structure

The Ariadne application builds and solves a variety of maze puzzles. a) When running the regular application Ariadne.exe, you can control the maze layout, its shape, additional content etc. via a "Details" panel. b) The Ariadne.scr file can be installed as a screen saver.

[Ariadne: Figure from Greek mythology. Ariadne helped Theseus escape from the maze where the Minotaurus was held.]

Screen Saver Configuration and Control

Use the Screen Saver "Settings" panel to configure the options of your screen saver (see the "[Option:]" tags below).

The Screen Saver accepts a few keystroke commands:

All other keystrokes and mouse buttons will terminate the screen saver.

There are several components for specific responsibilities and most of them have many optional features.

The Maze

The maze fills a rectangular region in a window. In screen saver mode, the display is filled completely.

The maze has a tree-like topological structure. Any square can be reached from every other square by exactly one path. There are no circles (paths leading from a square to itself).

The maze builder algorithm starts at an arbitrary square and adds it to the "visited" region. From then on, walls (whose state is initially undecided) between one visited and one not-visited square are opened until all squares have been reached. The remaining walls are closed.

Only closed walls are painted; open walls (also called "doors") are not painted.

[Option:] Usually, all walls of the empty maze are painted before the solver starts. There is an option by which two alternative modes can be activated: In one mode, no walls are painted at all (they have zero width); in the other mode, only the walls around visited squares are painted.

Images and other Reserved Areas

A plain maze fills the whole area. However, some regions may be reserved for additional controls or images. These reserved areas do not touch directly and the maze flows closely around them.

[Option:] You can specify a folder from which the Screen Saver chooses one or more foreground images (JPG, PNG, GIF) that will be displayed.

[Option:] You can select if a background image (from the same or a different image folder) is drawn behind the maze. Even then, only 20% of the mazes will have a background image (unless the number of foreground images is 0).

[Option:] You can select whether the Screen Saver displays a small info panel showing the maze dimension, solver name and run-time statistics.

Note: When both options for displaying foreground and background images are active, not all mazes will display a foreground image. The chance of having no foreground image is 20% if there is a background image and 5% otherwise.

Irregular Mazes

Usually, the constructed maze is "regular", uniformly random, i.e. the chances that a specific wall between two adjoining squares are evenly distributed.

In an irregular maze, some directions are preferred over other directions when opening the walls. The choice may depend on the square's location and on the opened/closed state of other walls.

[Variants:] There are 20 different methods or patterns of irregular mazes. e.g.:

[Option:] You can select whether irregular mazes may be built. If so, five percent of the mazes built in screen saver mode will be irregular. The irregular choice will be applied to 80% of the walls.

[Variants:] An irregular pattern may also be applied to part of the maze area only; the remainder is regular. That part is defined by the inside (or outside) of an Outline Shape (see next section). If an outline shape is already used for building the maze, that same shape is used for the irregular pattern, as well. Otherwise, a new outline shape may be used for the irregular pattern only. Another variant is a combination of two different irregular patterns on the inside and outside of the outline shape.

Outline Shapes

This option builds continuous closed walls around invisible shapes, e.g. a circle or a silhouette bitmap image (black on white). Only one wall will be opened so that a path can run into the shape. When the solver (see below) reaches the (closed) outline of the shape, it will run around it and the shape's contour will become visible. When the solver finds the entry into the shape, it will be filled from the inside but the solver cannot leave the shape as there is no second exit.

Usually, an outline shape is one contiguous shape, like a circle, a square or another polygon. However, an outline shape can also be any pattern that defines an inside and an outside. Separate regions are all treated the same way, i.e. each is surrounded by closed walls with a single entry.

[Variants:] There are 72 kinds of outline shapes, most of them with many variants, grouped into twelve mayor types:

While the patterns evoked by an Irregular Maze Builder come from following preferred directions (if possible), the rules defined by an outline shape are very strict. They take precedence over the irregular preferences.

[Option:] You can select whether outline shapes are placed into the maze. If so, 80% of the screen saver mazes will contain an outline shape.

Embedded Mazes

The outline shapes described above can also be used to create another maze within the main maze. These embedded mazes need to be totally connected and will include any area that is totally enclosed. Neither the main maze nor the embedded maze must fall apart into separate areas that are not connected. The two mazes are separated by a contiguous wall.

The embedded maze has its own solver (usually with a different strategy than the main maze solver). The paths in an embedded maze will be painted with different colors than in the main maze.

[Option:] You can select whether embedded mazes are generated. If so, 15% of the screen saver mazes will contain an embedded maze.

Solver Strategies

The solver tries to find a solution path between the start square and the target square. Some strategies are deterministic, the others make random choices. Some need to know the location of the target square, some don't. Most keep a memory of the squares they have already visited.

There are three general types of strategies: Backtrackers, Flooders and Walkers .

Backtrackers go forwards until they are caught in a dead end. Then they go backwards up to a fork with another door they have not yet passed. There the go forwards, then backwards, and so on. A backtracker can solve any maze.

Flooders follow several concurrent paths in parallel. For every door at a fork, new open paths are created. A flooder can solve any maze without ever going backwards.

Walkers have no memory of visited squares; they decide solely on their current position and direction. Two of these implement a classical maze solver algorithm: "Walk through the maze while always touching the wall at your right/left hand side." This strategy can solve any tree-shaped maze but may be caught in a circle.

The visited paths are painted in two colors: Forward steps are painted in a bright color, backward steps and areas completely covered by a flooder are painted in a dull color. Two colors with clearly different hue are selected. When the solution path is found, it is painted in a brighter variant of the forward color.

[Variants:] There are 21 "normal" maze solver strategies:

The classical backtracker algorithm; it walks forward as long as possible, making random choices at a fork. When there is no continuation, it walks back to the latest fork and chooses another path that has not yet been visited (this is called "backtracking").
Another backtracker; at a fork, this one prefers the square that is nearest to the target square (measuring the geometric distance).
This backtracker tries to get closest to the square directly opposite of the start square.
Walks through the maze while staying in touch with the right-hand wall.
Walks through the maze while staying in touch with the left-hand wall.
The classical flooder algorithm: For every step, choose an arbitrary open path at random.
This Flooder chooses to continue the open paths in a round-robin sequence, i.e. between two steps on the same path, all other paths are continued, as well.
From all currently visited paths, this flooder chooses the path closest to the start square.
This flooder chooses the path farthest away from the start square.
This flooder chooses the path closest to the target square.
This flooder chooses the path closest to the square directly opposite of the start square.
This flooder chooses the path farthest away from the target square.
This flooder chooses the path closest to the center of the maze.
This flooder chooses the path farthest away from the center of the maze.
This flooder checks all continuations on the open paths and chooses the one with the greatest (relative) distance gain: It chooses the path for which d'/d is minimal, where d is the distance of the current square (on that path) from the target square and d' is the distance of the next square on the same path.
This flooder works essentially like the ForwardFlooder, but it chooses the path continuation with maximal d'/d ratio.
This variant of the ForwardFlooder may also choose a path other than the best one. The "bad" path is chosen in one out ouf twenty steps.
This variant of the BackwardFlooder may also choose a path other than the best one. The "bad" path is chosen in one out ouf twenty steps.
This flooder is based on the maze's tree structure. Starting with a trunk of thickness 1 and length 0, every step increases the path length by 1 and every fork divides the thickness by the number of branches. Among the currently thickest branches, the longest one is chosen.
This flooder works like the ThickestBranchFlooder with inverted precedence: Among the thinnest branches, the shortest one is chosen.
This flooder selects one of the two path ends closest to each other.

Efficient Solvers

Each of these solvers also has an "efficient" variant. These employ an algorithm that detects dead ends and avoids these areas. An area is identified as a dead end if the squares visited by the solver (plus any reserved areas and the maze boundary) form a closed line around it.

Dead end squares are painted with dark gray dots.

Heuristic Solvers

There is also a "heuristic" variant of every flooder solver. These try to guess how promising an area examined by any branch is. Basically, when one path reaches a dead end it gives a signal to every neighboring path. Thus, paths with less negative signals from their dead siblings will be preferred. With some strategies, especially those that tend to avoid getting close to the target, this heuristic gives a significant advantage.

Extreme Strategies

There are two additional "extreme" strategies that are, however, not used in screen saver mode or when "any" solver should be selected.

This "solver" has no memory at all. Every step is chosen randomly. It may take a very long time (several 100,000 steps) until the target square is found by pure chance.
Knows the solution path beforehand. Goes directly from start to target without any error.


The area visited by the RandomBacktracker (in a regular maze) is a good example of a fractal: The border is self-similar at different scales.

RightHandWalker and LeftHandWalker produce "inverted" paintings: One visits all areas to the right of the solution path, the other all areas to the left.

OppositeBacktracker and OppositeFlooder don't know the location of the target square. But as the start and target squares are always chosen close to opposite borders of the maze, they often produce similar results as the proximity guided solvers.

Outline shapes are completely obliterated when large sections of the maze are visited. An efficient solver will not paint all squares in the same color and the shape will still be visible.

The ThickestBranchFlooder advances on a chosen branch in one run up to the next fork; then another branch is better than the split branches at the fork. The percieved movement is rather "jumpy", even at moderate speed.

ForwardFlooder and BackwardFlooder tend to fill the whole maze, just like a HesitatingFlooder. That is because both solvers assign highest penalties to undesired steps near the target square: the BackwardFlooder assigns an extreme penalty (100%) to the last step onto the target square; the ForwardFlooder assigns very high penalties to backward steps close to the target. In that situation, both solvers will visit the whole rest of the maze before doing the one highly penalized required step.

RandomForwardFlooder and RandomBackwardFlooder are able to overcome these problematic situations because their choice is not fixed. Sometimes they may choose the path with higher penalties and thus make the necessary but locally unfavorable step.

In the SpreadingFlooder, the pair of paths closest to each other advances in parallel. When one path is split or gets closer to a different path, it forms a new partnership with the other closer partner.

Efficient Solvers often run for long stretches without error (i.e. without leaving the correct solution path), especially towards the end. It is not unlikely that such a run spans more than half or two thirds of the solution path. Even perfect runs without any error at all can be observed. Considering that an average path may have several dozens or even hundreds of forks, this is quite amazing.

Package Structure of the Ariadne Application

Summary of Options and Variants

That gives a very large number of pattern or style combinations:

3 × (1 + 27×4) × (1+72+24) × (21+15) × 2  =  2,283,768

The exact application of each variant is usually (with a few deterministic exceptions) influenced by random parameter values: outline shapes are generated dynamically, solvers choose arbitrary paths and the maze builder generates random patterns of walls.