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: 735
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