Haskell minigame: check solvability of a maze (updated)

Question

check :: String -> Int -> Int -> IO()
check map len n = do
    let current = searchMap map '@'
    if (flood map current Up len n)
        then printf "\nThis map is solvable. \n"
        else printf "\nThis map is unsolvable. \n"

flood :: String -> Int -> Direction -> Int -> Int -> Bool
flood map current direct len n = do
    let upward = current - n
    let downward = current + n
    let leftward = current - 2
    let rightward = current + 2
    if (current < 0 || current > len || (map !! current) == '*' || (map !! current) == 'x')
        then False
        else if (map !! current) == 't'
            then True
            else do
                case direct of
                    Up -> do
                        let newMap = replaceSign map current "x"
                        (flood map upward Up len n) || (flood map leftward Leftx len n) || (flood map rightward Rightx len n)
                    Down -> do
                        let newMap = replaceSign map current "x"
                        (flood map downward Down len n) || (flood map leftward Leftx len n) || (flood map rightward Rightx len n)
                    Leftx -> do
                        let row = findRow current n 0
                        if current < (row * n)
                            then False
                            else do
                            let newMap = replaceSign map current "x"
                            (flood map upward Up len n) || (flood map downward Down len n) || (flood map leftward Leftx len n)
                    Rightx -> do
                        let row = findRow current n 0
                        if current >= ((row + 1) * n)
                            then False
                            else do
                            let newMap = replaceSign map current "x"
                            (flood map upward Up len n) || (flood map downward Down len n) || (flood map rightward Rightx len n)

I am working on a project which needs to make a minigame. The player will need to input a map. Something like this:

* * * * * - - - - - - - - - - - - - - - - - - - * * * * * 
* * * * * b - - - - - - - - - - - - - - - - - b * * * * * 
* * * * * - * * * * * * * * * * * * * * * * * - * * * * * 
* * * * * - * * - - - - * * * * * - - - - * * - * * * * * 
* * * * * - * * - y y - * * * * * - y y - * * - * * * * * 
* * * * * - * * - - - - * * * * * - - - - * * - * * * * * 
* * * * * - * * * * * * - - b - - * * * * * * - * * * * * 
* * * * * - * * * * * * - * * * - * * * * * * - * * * * * 
@ - - - - - * * * * * * - * * * - * * * * * * p - - - - t 
* * * * * - * * * * * * - * * * - * * * * * * - * * * * * 
* * * * * - - - - - - - - * * * - - - - - - - - * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *  

I struggling in a function to determine whether the map is solvable or not. In the code, current means the current location the program is trying. len is the length of the String holding the map. n is the length of one line of the map. In the map, @ means the ball. - means roads that the ball can move on. b means bonus block (not related to this problem). * means obstacle. t means target p/o/y means blocks with special use (ball can stop there). My current approach is to use a function try to try recursively. The function will turn roads that have already tried into x and the function will return False if it hit x. When function hits obstacles (*) or boundaries of map it will try another two directions. Eg. if you are currently moving Up. Then it will try Leftx and Rightx. If it hits special blocks (p/o/y), it will try the other three directions. Eg. if you are currently moving Rightx, then it will try Up, Down, and Rightx. However, the program returns "Exception: stack overflow". Is it something wrong with my algorithm? How can I fix this?

Answer 1

The problem is that once your search has proceeded all the way right and up, so the map looks like this, with the current position the leftmost - in the first row:

* * * * * - - - - - - - - - - - - - - - - - - - * * * * *
* * * * * x - - - - - - - - - - - - - - - - - b * * * * *
* * * * * x * * * * * * * * * * * * * * * * * - * * * * *
* * * * * x * * - - - - * * * * * - - - - * * - * * * * *
* * * * * x * * - y y - * * * * * - y y - * * - * * * * *
* * * * * x * * - - - - * * * * * - - - - * * - * * * * *
* * * * * x * * * * * * - - b - - * * * * * * - * * * * *
* * * * * x * * * * * * - * * * - * * * * * * - * * * * *
x x x x x x * * * * * * - * * * - * * * * * * p - - - - t
* * * * * - * * * * * * - * * * - * * * * * * - * * * * *
* * * * * - - - - - - - - * * * - - - - - - - - * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *

you enter the following loop with no further x marks made to the map:

try map 10 Up ... =
  -- at top row, so we evaluate:
  (try map current Leftx len n) || ...
try map 10 Leftx ... =
  -- star to the left, so we evaluate:
  (try map current Up len n) || ...
try map 10 Up ... =
  -- at top row, so we evaluate:
  (try map current Leftx len n) || ...
-- and we're stuck in an infinite loop

The stack eventually overflows because Haskell is keeping track of all those right-hand sides of the || operator, though it never gets a chance to try any of them.

I think you'll need to either modify your algorithm to mark walls you've already tried, or maybe switch from working with a single path to flood filling all the non-stars -- if you hit the target while flood fillling, the maze is solvable.