Algorithm I Developed For Solving Any Given Maze

[mdchurchill 0]

It basically uses a breadth first search of the maze, while removing backwards paths if its a tree.

 

We represent a place (square) in the maze by its x and y coordinates:

 

> type Place = (Int, Int)

 

A direction, corresponding to a compass point

 

> data Direction = N | S | E | W

 

Geographic functions opposite and move will be useful throughout the course of investigating the mazes. Their definitions are given below:

 

> opposite :: Direction -> Direction

> opposite N = S

> opposite S = N

> opposite E = W

> opposite W = E

 

> move :: Direction -> Place -> Place

> move N (i,j) = (i,j+1)

> move E (i,j) = (i+1,j)

> move S (i,j) = (i,j-1)

> move W (i,j) = (i-1,j)

 

We'll represent a piece of wall by a place and a direction. For example, ((3,4), N) means that there is a wall to the North of (3,4), and to the South of (3,5).

 

> type Wall = (Place, Direction)

 

A size of (x,y) represents that the squares are numbered (i,j) for i <- [0..x) and j <- [0..y).

 

> type Size = (Int, Int)

 

Here we shall define the given initial representation of mazes. Note that this module is independent and that the actual representation of the mazes is not used in the solving or drawing of mazes – the ‘interface’ of this module with the outside world contains three functions – makeMaze, which takes a list of walls and produces a maze; hasWall, which returns whether there is a wall in a specific place and direction; and sizeOf, returning an ordered pair representing the size of the maze. This is reflected in the module definition:

 

We'll represent a maze by its size and a list of its walls.

 

> data Maze = AMaze Size [Wall]

 

The list of walls will be complete in the sense that we record both sides of

the wall; for example, if the list includes ((3,4), N), then it will also

include ((3,5),S).

 

This function creates a maze given its size and a list of walls; the list of

walls might not be complete in the above sense.

 

> makeMaze :: Size -> [Wall] -> Maze

> makeMaze (x,y) walls =

> let boundaries = -- the four boundaries

> [((0,j), W) | j <- [0..y-1]] ++ -- westerly boundary

> [((x-1,j), E) | j <- [0..y-1]] ++ -- easterly boundary

> [((i,0), S) | i <- [0..x-1]] ++ -- southerly boundary

> [((i,y-1), N) | i <- [0..x-1]] -- northerly boundary

> allWalls = walls ++ boundaries ++ map reflect (walls ++ boundaries)

> in AMaze (x,y) allWalls

 

The following function "reflects" a wall; i.e. gives the representation as seen from the other side; for example, reflect ((3,4), N) = ((3,5),S)

 

> reflect :: Wall -> Wall

> reflect ((i,j), d) = (move d (i,j), opposite d)

 

The following function tests whether the maze includes a wall in a particular direction from a particular place:

 

> hasWall :: Maze -> Place -> Direction -> Bool

> hasWall (AMaze _ walls) pos d = (pos,d) `elem` walls

 

The following function returns the size of a maze:

 

> sizeOf :: Maze -> Size

> sizeOf (AMaze size _) = size

 

We shall now look at a functional algorithm to solve a given maze. The type returned will be a path:

 

> type Path = [Direction]

 

So solveMaze takes a maze, a starting position, an end position, and returns a path between those two points. solveMaze shall make use of a subsidiary function, solveMazeIter.

 

solveMazeIter works by maintaining a list of partial solutions – a partial solution being a place in the maze coupled with a path that can be used to get to that position in the maze from the start. The initial list shall merely consist of a singleton partial solution – namely the start position and the empty list – i.e. the start position and the path to get from the start position to the start position.

 

solveMazeIter then processes each element of the list (i.e. each partial solution) by replacing it with further partial solutions. It shall examine each element of the list and add all partial solutions that can be reached from that position to the end of the list. Once all entries of the list have been examined, either the target would have been found or the maze is impossible. This seems a very elegant, linear way to search for a solution to the problem and will hence be the one I use in solving mazes.

 

So our subsidiary function, solveMazeIter is to take a maze, the target location, and a list of partial solutions, and return a path (when one is found.)

 

> solveMaze :: Maze -> Place -> Place -> Path

> solveMaze maze start target = solveMazeIter maze target [(start, [])]

 

> solveMazeIter :: Maze -> Place -> [(Place, Path)] -> Path

> solveMazeIter maze target ((here,path):partials)

> | here == target = path

> | otherwise = solveMazeIter maze target (partials++expOut)

> where expOut = (if noWall N then [(move N here, path++[N])] else []) ++

> (if noWall E then [(move E here, path++[E])] else []) ++

> (if noWall S then [(move S here, path++)] else []) ++

> (if noWall W then [(move W here, path++[W])] else [])

> noWall d = if (hasWall maze here d) then False else True

 

Here expOut returns the list of locations accessible from the position being examined. The noWall subfunction has been used for elegance of layout.

 

solveMaze can successfully solve the first maze, and gives an output of

 

Main> solveMaze smallMaze (0,0) (3,2)

[E,N,E,S,E,N,N]

(44498 reductions, 73023 cells)

 

Main> solveMaze largeMaze (0,0) (22,21)

 

(59830457 reductions, 93059917 cells, 2526 garbage collections)

ERROR - Garbage collection fails to reclaim sufficient space

 

We can see that this solution works by inspection. However, solveMaze fails to solve the largeMaze in any reasonable amount of time, and in fact cannot be handled by the Hugs interpreter. The program above, therefore, is not efficient enough. We then increase the efficiency by having a subsidary list of places we’ve already visited, and not visiting them again (as they would be longer than any path we already have.

 

Complexity Analysis: The maximum number of times solveMazeIter is called is the number of squares of the maze, i.e. m*n. For each of these iterations, the hasWall function is called four times, each of which in turn requires a linear searching of the list of walls, of which there can be a maximum of 2*m*n. Therefore the order of this function over a maze of size m*n is O((m*n)^2)

[Brian1405241474 0]

Wow. Very nice!

[Atheos 0]

Hmm i think it have a bug. I'll check it more carefully later, now i go shopping .