CODEWITHSUNDEEP
algorithmhaskellfunctional-programming
CowNorris
CowNorris

Reputation: 432

Maze Solver in Haskell - Determine if maze is unsolvable

I have been recently trying to create a maze-solver in Haskell and I have managed to piece together a mostly working algorithm. However I am lost as to how to determine if a given maze is impossible to solve.

solveMazeQuickly :: Maze -> Place -> Place -> Path
solveMazeQuickly maze start target = fastSolveMazeIter maze target [(start, [])] [start] -- last is the elem of visited nodes along with its paths

fastSolveMazeIter :: Maze -> Place -> [(Place, Path)] -> [Place] -> Path
fastSolveMazeIter maze target (x:xs) visited -- last argument is the list of visited places
 | (tenatives == []) && (length (x:xs) == length (visited)) = error "unsolvable maze"
 | currentPos == target = pathPos -- return the path if we're already there
 | otherwise = fastSolveMazeIter maze target (xs++tenatives) (visited++(map fst tenatives))
   where currentPos = fst x -- current position
         pathPos = snd x -- the path to current position
         tenatives = scan currentPos pathPos -- the 'successful' tried paths
         try pos curPath d
          | ((hasWall maze pos d) == False) && ((nextPos `elem` visited) == False) = [(nextPos, curPath++[d])] -- disregard visited positions
          | otherwise = []
            where nextPos = move d pos
         scan pos curPath = (try pos curPath N) ++ (try pos curPath S) ++ (try pos curPath E) ++ (try pos curPath W) -- try the four directions

The co-ordinate system is based on each 'squares' of the maze. Each position has walls that can be on its 4 sides, and this information is stored inside the Maze datatype.

The algorithm keeps track of the places that it has visited, as well as storing a list of the places that it can access, together with the path to that point from the start.

Thus far, I have attempted to take into account for an unsolvable maze with a condition that if the visited positions are equal in size to the accessible positions, with no possible way to continue the solution (tentative == []), then the maze is unsolvable. However that does not seem to do the trick.

When attempting to solve the following impossible maze

+--+--+--+
|     |  |
+  +  +--+
|  |     |
+  +--+  +
|        |
+--+--+--+

Haskell returns "Maze Practical\Main.lhs:(88,3)-(99,118): Non-exhaustive patterns in function fastSolveMazeIter" instead of the intended error message.

Upvotes: 3

Views: 743

Answers (1)

Paul Johnson
Paul Johnson

Reputation: 17786

fastSolveMazeIter includes the pattern (x:xs) in its argument list. What should happen if the argument is empty?

Upvotes: 1

Related Questions