Maze

Solving mazes is a great time-pass, if you “too” have nothing to do just try to solve this maze made by me (very easy one, can be solved within few seconds)

Very easy example of maze

Since I am writing about mazes, there must be something mathematical about them. Indeed “solving a maze” is a NP-complete problem [Non-deterministic Polynomial-time solvable problem], one of most popular class of problems in Theoretical Computer Science. But, no surprise here, since lot of puzzles like Minesweeper, sudoku etc. too are NP-complete.

Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology.

Mazes containing no loops are known as “standard”, or “perfect” mazes, and are equivalent to a tree in graph theory. Thus many maze solving algorithms are closely related to graph theory. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree (dead ends become the leaves of the tree.).

To make my maze I used “adding walls algorithm” i.e. I laid a set of obstructions within an open area.  Can you tell whether my maze above is “perfect” one??

As it turns out, there are various maze generation as well as maze solving algorithms. A detailed discussion of these can be found at: http://www.astrolog.org/labyrnth/algrithm.htm

Also, there is an interesting article on Maze solving using image analysis: http://www.crisluengo.net/index.php/archives/277