backtracking in haskell

Posted by dmindreader on Stack Overflow See other posts from Stack Overflow or by dmindreader
Published on 2010-04-12T16:06:42Z Indexed on 2010/04/13 2:02 UTC
Read the original article Hit count: 740

Filed under:
|
|

I have to traverse a matrix and say how many "characteristic areas" of each type it has.

A characteristic area is defined as a zone where elements of value n or >n are adjacent.

For example, given the matrix:

0 1 2 2
0 1 1 2
0 3 0 0

There's a single characteristic area of type 1 which is equal to the original matrix:

0 1 2 2
0 1 1 2
0 3 0 0

There are two characteristic areas of type 2:

0 0 2 2    0 0 0 0
0 0 0 2    0 0 0 0
0 0 0 0    0 3 0 0

And one characteristic area of type 3:

0 0 0 0 
0 0 0 0
0 3 0 0 

So, for the function call:

countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] 

The result should be

[1,2,1]

I haven't defined countAreas yet, I'm stuck with my visit function when it has no more possible squares in which to move it gets stuck and doesn't make the proper recursive call. I'm new to functional programming and I'm still scratching my head about how to implement a backtracking algorithm here. Take a look at my code, what can I do to change it?

move_right :: (Int,Int) -> [[Int]] -> Int -> Bool
move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True
               | otherwise = False

move_left :: (Int,Int) -> [[Int]] -> Int -> Bool
move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True
               | otherwise = False

move_up :: (Int,Int) -> [[Int]] -> Int -> Bool
move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True
               | otherwise = False

move_down :: (Int,Int) -> [[Int]] -> Int -> Bool
move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True
               | otherwise = False

imp :: (Int,Int) -> Int
imp (i,j) = i


number_of_rows :: [[Int]] -> Int
number_of_rows i = length i

number_of_columns :: [[Int]] -> Int
number_of_columns (x:xs) =  length x

consult :: (Int,Int) -> [[Int]] -> Int
consult (i,j) l = (l !! i) !! j

visited :: (Int,Int) -> [(Int,Int)] -> Bool
visited x y = elem x y

add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
add x y = x:y

visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)]
visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
               | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
               | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
               | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
               | otherwise = vis

© Stack Overflow or respective owner

Related posts about haskell

Related posts about backtracking