Haskell回溯递归

Question

我正在使用Haskell实现这个功能。

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

当到达“目标”时，我能够获取列表，但如果目标不可访问，则列表未更新。例如：

...#@                           !!!#@
..#..                           !!#..
.##.#     it should return      !##.#
...#.                           !!!#.

我的代码如下

path maze x y
    | x >= length (head maze) = (False, maze)
    | y >= length maze = (False, maze)
    | x < 0 = (False, maze)
    | y < 0 = (False,maze)
    | check maze x y '+' = (False, maze)
    | check maze x y '#' = (False,maze)
    | check maze x y '!' = (False, maze)
    | check maze x y 'G' = (True,maze)
    | fst east = (True,snd east)
    | fst south = (True, snd south)
    | fst west = (True, snd west)
    | fst north = (True, snd north)
    | fst noWay = (True, snd noWay)
    | otherwise = (False, maze)
            where 
                    noWay = path (changeVal maze x y '!') x (y+1)
                    north = path(changeVal maze x y '+') x (y-1)
                    south = path (changeVal maze x y '+') x (y+1)
                    east = path (changeVal maze x y '+') (x+1) y
                    west = path (changeVal maze x y '+') (x-1) y

我没有得到结果。我是Haskell的新手，能否有人给我一些帮助，这样我就可以解决这个愚蠢的问题。

- raselc

---

“noWay”/“!”这部分是你添加的吗？它可能会出现两个问题：首先，你会使用“noWay”向下移动，但你已经尝试过并发现在“south”方向下不可能实现 - 所以这种情况永远不应该匹配，并且我认为你永远不会标记任何东西为“！”。为什么不在最后的“otherwise”情况中标记它（删除“noWay”情况）- 这应该可以解决问题。如果你在某个地方发布完整的代码（带有示例），我很乐意检查它;) - Random Dev

这是整个代码。changeVal函数会改变坐标上的值，check函数会检查坐标上的值。 - raselc

Answer 1

立即，您问题的原因似乎是

| otherwise = (False, maze)

使用原始的maze而不是返回一个已更新的迷宫。然而，即使将其替换为snd noWay也无法得到所需的输出。(我认为它只会在您的起点以南部分标记!)

有一个更大的问题：当继续进行下一个递归步骤时，你的函数没有保留前一个步骤放置的标记，而是从原始的maze再次开始。相反，下一个递归步骤需要以前一个步骤产生的最终迷宫标记为起点。比如（因为你的守卫走东 -> 南 -> 西 -> 北），你需要让south从east结束的地方开始，类似于：

south = path (snd east) x (y+1)

如果你把所有路线都类似地修复好，那么就不需要使用noWay（此时没有未标记的地方需要检查）。相反，如果north情况失败了，它会标记除初始点外的所有地方，因此你可以执行以下操作。

| otherwise = (False, changeVal (snd north) x y '!')

- Ørjan Johansen