News for hackers. Stuff that matters.
Re:Programming Interview Question: Eight Queens by tel on Tuesday December 31, 2013 @07:44PM (#6993623)
I love the Haskell version of this because non-deterministic computation via (depth-first) search is embodied by the list monad!

The preliminaries are that we represent a board position containing N queens on an NxN board by a list of row positions in each of N columns.

    newtype Board = Board [Int] deriving ( Eq, Show )
    emptySolution = Board []
Then, given any particular NxN board with M queens in first M columns that is a solution to M-queens, we can generate the list of possible new boards with (M+1) queens. We try all possible row positions for the new column excepting the rows where queens already exist.

    attempts :: Int -> Board -> [Board]
    attempts n (Board queens) = 
      map (\r -> Board (r : queens)) ([0 .. n - 1] \\ queens)
And we prune out the ones where the new queen has a diagonal conflict.

    valid :: Board -> Bool
    valid (Board []) = True
    valid (Board (q:cols)) = 
      and $ map (\(n, c) -> abs (q - c) /= n) (zip [1..] cols)

      -- this is a bit clever, as we walk back through
      -- the previous columns, if the absolute difference
      -- between the row position of the new queen and
      -- an old queen is ever the count of the column 
      -- we're in, then it must be in a diagonal line
      -- from the new queen
All of the above is pretty standard, but the fun part is using the list monad to structure a search. Each bind (<-) in do-notation can be thought of as non-deterministically setting a particular choice from the right side to the name on the left

    queens :: Int -> [Board]
    queens n = search n [emptySolution] where
      search 0 boards = boards -- no more queens to add
      search k boards = do
        board <- search (k - 1) boards -- find a smaller solution
        filter valid (attempts board)  -- try all possible extensions,
                                       -- remove the bad ones

    >>> length (queens 8)
    92
Finally, the pattern of `search` is really common, it's just iterating the generation of attempted solutions. We can write it with the built-in function `Control.Monad.foldM` or another common utility combinator, `iterateM`

    iterateM :: Monad m => (a -> m a) -> a -> [m a]
    iterateM f x = iterate (f =<<) (return x)

    queens n = iterateM (filter valid . attempts n) emptySolution !! n
Finally, it's worth noting that there's nothing special about the list monad's implementation. It's easy to rewrite it without using the typeclass.

    -- this is the list monad definition
    instance Monad [] where
      return a = [a]
      xs >>= f = concat (map f xs)

    iterateList :: (a -> [a]) -> a -> [[a]]
    iterateList f x = iterate (concat . map f) [x]

There are no comments on this comment yet.