Day: December 25, 2015

https://en.wikipedia.org/wiki/Eight_queens_puzzle

This is a very popular problem, and let’s see how it can be treated with Haskell.

https://wiki.haskell.org/99_questions/Solutions/90

First, we generate all possible arrangements recursively.

queens :: Int -> [[Int]]
queens n = generate n
    where generate 0      = [[]]
          generate k      = [q : qs | q <- [1..n], qs <- generate (k-1)]

main = do
    print $ queens 3

[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]

Here, [x,y,z] means we have queens at (a,x), (b,y), (c,z).

Obviously, we can place only one queen for each raw, so the patters containing the same number must be eliminated.

queens :: Int -> [[Int]]
queens n = filter test (generate n)
    where generate 0      = [[]]
          generate k      = [q : qs | q <- [1..n], qs <- generate (k-1)]
          test []         = True
          test (q:qs)     = isSafe q qs && test qs
          isSafe   try qs = not (try `elem` qs)

main = do
    print $ queens 3

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

The function elm returns True if the list qs contains an item equal to the argument try.

Now, the last thing to check is if the two queens are in the same diagonal.

queens :: Int -> [[Int]]
queens n = filter test (generate n)
    where generate 0      = [[]]
          generate k      = [q : qs | q <- [1..n], qs <- generate (k-1)]
          test []         = True
          test (q:qs)     = isSafe q qs && test qs
          isSafe   try qs = not (try `elem` qs || sameDiag try qs)
          sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

main = do
    print $ queens 3

[ ]

This is OK, because we know that there is no solution for n=3. So let’s try again with n=4.

[[2,4,1,3],[3,1,4,2]]