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]]