Haskell Maze solving algorithm

Question

I am trying to implement a maze solver based on the algorithm described in the below link in Haskell.

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

I am pretty new to haskell and functional programming, and I basically try to code the algorithm as described in the link, I tried to go through many other resources online but I am stuck in the part where the walking stops when the goal (It doesn't stop, it back tracks to the origin) is reached, and I am unable to unmark the bad positions in the maze.

The maze looks like

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

my code is as follows

       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

the isSafe function just checks for bounds, the isChar is just character matching at a given x,y position and the replaceCharInMaze function replaces the character at the x,y position with the supplied character.

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

So, I have two problems

I am not able to persist the un-marking being done at the Otherwise case to the next recursion call, how do I go about persisting the state of the maze, so that even the un-marked state be part of the solution?
Then as the algorithm proceeds, It walks till the goal and comes back to the start, how to stop this from happening?

As I am new to Haskell and algorithms, I looked in to topics such has state monads, which seemed to be like the solution, but I am not quite sure about proceeding with it, I also tried looking into other stack overflow posts, but couldn't find anything that would help me.

The output for a maze obtained during the trace statement is as follows

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

But it doesn't stop there it comes backtracks to the origin and prints the output as

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

ackien · Accepted Answer · 2014-08-02 22:17:57Z

1

Here's what happens when you run your program with your example. The first four guards are clearly False, so not much happens up to that point. It evaluates walkNorth by recursing once, in order to find that fst walkNorth is also False. Then it evaluates walkEast, which takes a while, since eventually that leads to the goal. It finds that fst walkEast is True, so it returns (True,markedList). It's important to realise that the markedList in the returned pair has only been 'marked' once (hence there is a single '+' in your output). Lots of 'markings' have been happening on the way to the goal, but those aren't visible from where the program returns its output. Each time you pass a markedList into one of the walkXXX functions, you're essentially creating a new list, with an additional marking, which can only be seen in the function call you're passing it into. What you actually want is the maze with the markings at the point where it's been solved. At the end of the day, the walkXXX functions either return (False,maze) when walking in the XXX direction doesn't lead to the goal (because the 1st or 3rd guard evaluates to True), or (True,maze) if it does lead to the goal (the 2nd guard evaluates to True), in which case, maze at that point will have all the correct markings. So instead of returning markedList for the fst walkXXX cases, return snd walkXXX. i.e.

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

Your first question is a bit complicated. I think what you want is to change your walkXXX definitions to something very roughly like this:

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)

and I'll let you fill in the last one. If you are walking east, you know that you've tried walking north and not found the goal, so you can unmark it, and so on. (This isn't quite going to work, at the very least because it will probably try to replace walls and characters outside of the maze, but the idea is there.)

You seem to be not yet accustomed to Haskell's lack of mutable state and frequent recursion. Some other things (I'm not certain about these): I don't think your otherwise case ever runs, and it doesn't really do anything -- try taking it out and see what happens; I also don't think the Trues in your (True,markedList) pairs ever have any effect -- try changing them to False.

edited Aug 2, 2014 at 22:17

answered Aug 2, 2014 at 16:19

ackien

5911 gold badge5 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Pradeep Samuel Daniel Over a year ago

Hi @ackien, Thanks for your reply, It helped a lot, Actually I missed a point, that only when you cant move in any direction, you should un-mark the cell with !, but other changes made it work now :), its stopping at the solution but the un-marking is still not working.

Pradeep Samuel Daniel Over a year ago

walkNorth = findPath' x (y-1) (replaceCharInMaze maze x y '+')                           walkEast = findPath' (x+1) y (replaceCharInMaze maze x y '+')                           walkSouth = findPath' x (y+1) (replaceCharInMaze maze x y '+')                           walkWest = findPath' (x-1) y (replaceCharInMaze (replaceCharInMaze maze x y '!') x y '+')

Pradeep Samuel Daniel Over a year ago

solution if G is reachable

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

if its not reachable the output is

!--#--###--#----#- ##---#----##---#-- ####-#-#----#--#-- ---#---#-###@--#-- -#-####---######## -#------##-------- -################- ------------------

Pradeep Samuel Daniel Over a year ago

Hi @ackien, I made it work finally, as you said I dumped the otherwise and added a "not (fst walkWest)" condition which back tracks to north, thanks a tonne for your help! :-)

Collectives™ on Stack Overflow

Haskell Maze solving algorithm

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related