algorithm - Haskell 中的 Maze Solver - 确定迷宫是否无法解决

Question

我最近一直在尝试在 Haskell 中创建一个迷宫求解器，并且我已经设法拼凑出一个大部分可用的算法。但是，我不知道如何确定给定的迷宫是否无法解决。

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

坐标系基于迷宫的每个“正方形”。每个位置的 4 个边都有墙，此信息存储在 Maze 数据类型中。

该算法会跟踪它访问过的地点，并存储它可以访问的地点的列表，以及从一开始到该点的路径。

到目前为止，我已经尝试考虑一个无法解决的迷宫，条件是如果访问位置的大小等于可访问位置的大小，则无法继续解决方案(tentative == [ ])，则迷宫无解。然而，这似乎并不能解决问题。

当试图解决以下不可能的迷宫时

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

Haskell 返回“Maze Practical\Main.lhs:(88,3)-(99,118): Non-exhaustive patterns in function fastSolveMazeIter”而不是预期的错误消息。

Answer 1

fastSolveMazeIter 在其参数列表中包含模式 (x:xs)。如果参数为空会发生什么？