Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Simple solver for the n-queens problem in Curry

View gist:158634
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
-- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.