The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.
The task is to implement the extended version, queens :: Int -> [[Int]]; given an integer specifying the dimension of the chess board, it returns
all valid solutions.
Since it’s a well-established problem, many standard techniques exist, such as those listed at https://rosettacode.org/wiki/N-queens_problem#Haskell.
I have reprinted two versions I am quite fond of. Now that there are multiple versions available, I am curious about their performance, so I used the
following main function, compiled with -O, to do simple evaluation, and the result is attached along with the corresponding source code.
import Control.Monad import Data.List (delete) queens n = map fst $ foldM oneMorequeens (,[1..n]) [1..n] where oneMorequeens (y,d) _ = [(x:y, delete x d) | x <- d, safe x] where safe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] y] -- 73712 -- 3.256558s