Instantly share code, notes, and snippets.

# sebfisch/gist:158634 Created Jul 30, 2009

What would you like to do?
Simple solver for the n-queens problem in Curry
 -- Simple solver for the n-queens problem in Curry. -- -- A placement is represented as permutation of [1..n], each list -- element represents the placement of a queen in the column -- corresponding to its index. import Integer ( abs ) -- Solutions are computed using a lazy generate-and-test approach: -- candidate solutions are created lazily and admissible solutions -- filtered out using a guard. -- queens :: Int -> [Int] queens n | safe qs = qs where qs = permute [1..n] -- As queens are placed in different rows and columns automatically, -- we only check that they don't capture each other diagonally. -- safe :: [Int] -> Bool safe qs = and [ j-i /= abs (q_j-q_i) | (i,q_i) <- iqs, (j,q_j) <- iqs, i < j ] where iqs = zip [1..] qs -- Candidate solutions are computed using a non-deterministic -- operation to permute a list. -- permute :: [a] -> [a] permute [] = [] permute (x:xs) = insert x (permute xs) insert :: a -> [a] -> [a] insert x l = x : l insert x (y:ys) = y : insert x ys