Maze-solving algorithm

A maze-solving algorithm is an automated method for solving a maze. The random mouse, wall follower, Pledge, Tarry's, and Trémaux's algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end filling and shortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once. Mazes containing no loops are known as "simply connected", or "perfect" mazes, and are equivalent to a tree in graph theory. 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.

A maze-solving algorithm is an automated method for solving a maze. The random mouse, wall follower, Pledge, Tarry's, and Trémaux's algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end filling and shortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once. Mazes containing no loops are known as "simply connected", or "perfect" mazes, and are equivalent to a tree in graph theory. 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. ==Tarry's algorithm== Tarry’s algorithm, published by Gaston Tarry in 1895¹ in Le problème des labyrinthes , is a method for traversing a maze or connected undirected graph with no prior knowledge of the maze layout. It is similar to Trémaux’s algorithm in that it uses maze marking to record exploration progress. The algorithm guarantees complete traversal and termination; each edge is traversed at most twice, once in each direction. It can be expressed as a single rule, described by MacTutor as “particularly suitable to computer implementation”: Do not exit from an intersection the way you came in until all other exits have been explored. It is now considered to be an early depth-first-search-like procedure. boolean[][] maze = new boolean[width][height]; // The maze boolean[][] wasHere = new boolean[width][height]; boolean[][] correctPath = new boolean[width][height]; // The solution to the maze int startX, startY; // Starting X and Y values of maze int endX, endY; // Ending X and Y values of maze public void solveMaze() { maze = generateMaze(); // Create Maze (false = path, true = wall) // Below assignment to false is redundant as Java assigns array elements to false by default, but it is included because other languages may not behave the same. for (int row = 0; row Point src, dst;// Source and destination coordinates // cur also indicates the coordinates of the current location int MD_best = MD(src, dst);// It stores the closest MD we ever had to dst // A productive path is the one that makes our MD to dst smaller while (cur != dst) { if (there exists a productive path) { Take the productive path; } else { MD_best = MD(cur, dst); Imagine a line between cur and dst; Take the first path in the left/right of the line; // The left/right selection affects the following hand rule while (MD(cur, dst) != MD_best || there does not exist a productive path) { Follow the right-hand/left-hand rule; // The opposite of the selected side of the line } } ==See also== Maze Maze generation algorithm ==External links== Think Labyrinth: Maze algorithms (details on these and other maze-solving algorithms) MazeBlog: Solving mazes using image analysis Video: Maze solving simulation Simon Ayrinhac, Electric current solves mazes, © 2014 IOP Publishing Ltd.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372497842 under CC BY-SA 4.0; modifications have been made.