public
Last active

Efficient solver for the n-queens problem in Curry

  • Download Gist
gistfile1.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
-- Efficient 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.
 
-- The implementation uses a finite domain constraint solver which is
-- available in the Curry system PAKCS.
--
import CLPFD
 
-- A placement of n queens must consist of distinct numbers between 1
-- and n such that no queens capture each other diagonally.
--
queens :: Int -> [Int]
queens n | domain qs 1 n & all_different qs & safe qs
& labeling [FirstFailConstrained] qs
= qs
where qs = [ unknown | _ <- [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] -> Success
safe qs = andC [ (j-i) /=# (q_j-#q_i) & (j-i) /=# (q_i-#q_j)
| (i,q_i) <- iqs, (j,q_j) <- iqs, i < j ]
where iqs = zip [1..] qs
 
-- The safe predicate uses an auxiliary predicate for constraint
-- conjunction.
--
andC :: [Success] -> Success
andC = foldr (&) success

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.