board search in Haskell

index.hs

type Board = [[Char]]

data Link = Link { pos :: (Int, Int)
                 , vis :: [(Int, Int)]
                 , mat :: [Char] } deriving Show

neighbors :: Board -> Int -> Int -> [(Int, Int)]
neighbors b i j = [(x, y) | x <- [(i - 1) .. (i + 1)],
                            y <- [(j - 1) .. (j + 1)],
                            x > -1,
                            y > -1,
                            x < (length b),
                            y < (length (b !! 0)) ]

initial :: Board -> [Char] -> [Link]
initial b []     = []
initial b (c:cs) =
  let possible = [(i, j) | i <- [0..((length b) - 1)],
                           j <- [0..((length (b !! 0)) - 1)],
                           ((b !! i) !! j) == c ]
  in map (\c -> Link { pos = c, vis = [c], mat = cs }) possible


findSolution :: Board -> [Link] -> [Link] -> Bool
findSolution _ [] [] = False
findSolution b [] links = findSolution b links []
findSolution _ ((Link { pos = (i, j), vis = vs, mat = []} ):xs) links = True
findSolution b ((Link { pos = (i, j), vis = vs, mat = (m:ms)} ):xs) links =
  let ns = [Link { pos = (x, y), vis = [(x, y)] ++ vs, mat=ms }   | (x, y) <- (neighbors b i j),
                  (all (\v -> v /= (x, y)) vs),
                  ((b !! x) !! y) == m ]
  in findSolution b xs (links ++ ns)



testBoard :: Board
testBoard = [
  ['a', 'c', 'l', 'b'],
  ['r', 'e', 'b', 'u'],
  ['l', 'n', 'c', 's'],
  ['c', 'm', 'n', 'o']]
--
--
theDoot :: Board -> [Char] -> Bool
theDoot _ [] = True
theDoot b xs =
  let starting = initial b xs
  in findSolution b starting []