Алгоритм решения лабиринта Хаскелла

Я пытаюсь реализовать решатель лабиринта, основанный на алгоритме, описанном в приведенной ниже ссылке в Haskell.

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

Я довольно новичок в Хаскелле и функциональном программировании, и я в основном пытаюсь кодировать алгоритм, как описано в ссылке, я пытался пройти через многие другие ресурсы в интернете, но я застрял в той части, где ходьба останавливается, когда цель (она не останавливается, она возвращается к началу) достигнута, и я не могу найти ее. чтобы снять отметку с плохих позиций в лабиринте.

Лабиринт выглядит как 

.########
.......#.
#.####..#
#.#######
...#.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 и алгоритмах, я заглянул в такие темы, как монады состояний has, которые, казалось бы, были похожи на решение, но я не совсем уверен, что продолжу его, я также попытался заглянуть в другой стек переполнение сообщений, но не смог найти ничего, что помогло бы мне.

Выходные данные для лабиринта, полученные в ходе трассировки, выглядят следующим образом 

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

Но он не останавливается на этом, он возвращается к началу координат и выводит результат в виде 

+..#..###..#.
.#...#....##.
####.#.#.#.##
...#...#.#...
.#.####...##.
.#G.....#....
.############
....####.....
1 2
functional-programming recursion maze

1 ответ:

Вот что происходит, когда вы запускаете программу с вашим примером. Первые четыре охранника явно фальшивые, так что до этого момента мало что происходит. Он вычисляет walkNorth, рекурсируя один раз, чтобы найти, что fst walkNorth также ложно. Затем он оценивает walkEast, что занимает некоторое время, так как в конечном итоге это приводит к цели. Он находит, что fst walkEast истинно, поэтому он возвращает (True,markedList). Важно понимать, что markedList в возвращаемой паре был "помечен" только один раз (следовательно, в вашем списке есть один"+"). выход). На пути к цели происходит много "отметок", но они не видны оттуда, откуда программа возвращает свой вывод. Каждый раз, когда вы передаете markedList в одну из функций walkXXX, вы, по сути, создаете новый список с дополнительной маркировкой, которую можно увидеть только в вызове функции, в которую вы его передаете. На самом деле вам нужен лабиринт с отметками в том месте, где он был решен. В конце дня функции walkXXX либо возвращают (False,maze), когда хождение в направлении XXX не приводит к цели (потому что 1-й или 3-й охранник оценивает как True), или (True,maze), Если это действительно приводит к цели (2-й охранник оценивает как 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)
И я позволю тебе заполнить последнюю. Если вы идете на восток, вы знаете, что вы пробовали идти на север и не нашли цель, поэтому вы можете снять ее и так далее. (Это не совсем сработает, по крайней мере, потому что он, вероятно, попытается заменить стены и персонажей за пределами лабиринта, но идея есть.) Вы, кажется, еще не привыкли к отсутствию у Хаскелла изменчивого состояния и частой рекурсии. Некоторые другие вещи (я не уверен в этом они): я не думаю, что ваш случай otherwise когда-либо работает, и он действительно ничего не делает-попробуйте вынуть его и посмотреть, что произойдет; я также не думаю, что Trues в ваших парах (True,markedList) когда-либо имеют какой-либо эффект-попробуйте изменить их на False.
1