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)
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.
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??
Also, there is an interesting article on Maze solving using image analysis: http://www.crisluengo.net/index.php/archives/277