Maze

Standard

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)

New Doc 8_1

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

 

 

Advertisements

2 responses »

  1. Pingback: Mathematical Relations | Gaurish4Math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s