Haskell Maze求解算法

Question

我正在尝试基于Haskell中以下链接中描述的算法实现迷宫求解器。

http://www.cs.bu.edu/teaching/alg/maze/

我对haskell和函数式编程很新，我基本上尝试编码链接中描述的算法，我试图在线浏览许多其他资源，但我被困在目标行走停止的部分（它没有到达时，它会停止，它会回到原点的轨道），我无法取消标记迷宫中的不良位置。

迷宫看起来像

.########
.......#.
#.####..#
#.#######
...#.G...
##...####
#..######

我的代码如下

       findPath :: Int->Int->Maze->(Bool,Maze)
       findPath x y maze
            | not (isSafe maze x y) = (False,maze)
            | isChar maze x y 'G' = trace ("Solution: "++ show maze)(True,maze)
            | isChar maze x y '#' = (False,maze)
            | isChar maze x y '!' = (False,maze)
            | fst walkNorth = (True,markedList)
            | fst walkEast = (True,markedList)
            | fst walkSouth = (True,markedList)
            | fst walkWest = (True,markedList)
            | otherwise = (False,unMarkedList)
                where markedList = replaceCharInMaze maze x y '+'
                      unMarkedList = replaceCharInMaze maze x y '!'
                      walkNorth = findPath x (y-1) markedList
                      walkEast = findPath (x+1) y markedList
                      walkSouth = findPath x (y+1) markedList
                      walkWest = findPath (x-1) y markedList

isSafe函数只检查边界，isChar只是在给定的x，y位置进行字符匹配，而replaceCharInMaze函数用提供的字符替换x，y位置的字符。

isSafe :: [String]->Int->Int->Bool
isSafe list x y
    | y >= 0 && y < length (head list) && x >= 0 && x < length list && (isChar list xy '.' || isChar list x y 'G') = True
    | otherwise = False

所以，我有两个问题

1. 我无法在下一个递归调用中坚持在其他情况下完成取消标记，如何继续保持迷宫的状态，以便即使未标记的状态也是解决方案的一部分？
2. 然后随着算法的进行，它走到目标并回到起点，如何阻止这种情况发生？

由于我是Haskell和算法的新手，我查看了有状态monad的主题，这似乎就像解决方案一样，但我不太确定继续使用它，我也试着查看其他堆栈溢出帖子，但是不能找不到任何可以帮助我的东西。

在trace语句期间获得的迷宫的输出如下

+++#..###..#.
.#+++#+++.##.
####+#+#+#-##
...#+++#+#...
.#.####++.##.
.#G+++++#....
.############
....####.....

但它并不止于此它回溯到原点并将输出打印为

+..#..###..#.
.#...#....##.
####.#.#.#.##
...#...#.#...
.#.####...##.
.#G.....#....
.############
....####.....

Answer 1

以下是使用您的示例运行程序时会发生的情况。前四名后卫显然是假的，所以在那一点上没有多少事情发生。它通过递归一次来评估walkNorth，以便发现fst walkNorth也是假的。然后它评估walkEast，这需要一段时间，因为最终导致目标。它发现fst walkEast是真的，所以它返回(True,markedList)。重要的是要意识到返回对中的markedList只被'标记'一次（因此输出中只有一个'+'）。在通往目标的路上发生了很多“标记”，但是从程序返回其输出的位置看不到这些标记。每次你将markedList传递给walkXXX函数之一时，你实际上创建了一个新的列表，带有一个额外的标记，只能在你传入它的函数调用中看到。你真正想要的是带有标记的迷宫，它已经被解决了。在一天结束时，walkXXX功能要么返回(False,maze)，当沿XXX方向行走不会导致目标（因为第一或第三卫队评估为真），或(True,maze)，如果它确实导致目标（第二警卫评估为True），在这种情况下，maze将拥有所有正确的标记。因此，不要返回markedList为fst walkXXX案件，返回snd walkXXX。即

    | fst walkNorth = (True,snd walkNorth)
    | walkEast = (True,snd walkEast)
    | walkSouth = (True,snd walkSouth)
    | walkWest = (True,snd walkWest)

你的第一个问题有点复杂。我认为你想要的是将你的walkXXX定义改为非常类似的东西：

walkNorth = findPath x (y-1) markedList
walkEast = findPath (x+1) y (replaceCharInMaze markedList x (y-1))
walkSouth = findPath x (y+1) (replaceCharInMaze (replaceCharInMaze markedList x (y-1)) (x+1) y)

我会让你填写最后一个。如果你向东走，你知道你已经尝试向北走，没有找到目标，所以你可以取消标记，等等。 （这不太合适，至少因为它可能会尝试替换迷宫之外的墙壁和角色，但这个想法就在那里。）

你似乎还不习惯Haskell缺乏可变状态和频繁递归。其他一些事情（我不确定这些）：我不认为你的otherwise案件曾经运行过，它并没有真正做任何事情 - 尝试把它拿出去看看会发生什么;我也不认为你的True对中的(True,markedList)s有任何影响 - 尝试将它们改为False。