Fairly general constraint satisfaction forward search algorithm.

A variable assignment is a pair (var, value).
A variable constraint is a pair (var, [value]).  The list contains
permitted values.

The user defines types 'var' for the variables and 'value' for their
possible values.  The user supplies the conflict predicate:

  conflict :: (var,value) -> (var,value) -> Bool

which is true iff the pair of assignments are in conflict.

Then the following csp function solves the CSP.  It returns
[[(var,value)]], list of solutions.  It inputs: the conflict function
and the full list of variable constraints.

> csp :: ((var,value) -> (var,value) -> Bool) -> [(var, [value])] -> [[(var,value)]]
> csp _ [] = [[]]
> csp conflict ((var,values):constraints) =
>   do value <- values
>      subsolution <- csp conflict (elim (var,value) constraints)
>      return ((var,value):subsolution)
>   where
>   elim a cs = map elim1 cs
>     where elim1 (v,s) = (v, [x | x<-s, not (conflict a (v,x))])


Let's try it on the n-queen problem.

> queenconflict (q,p) (q',p') =
>   p==p' || abs(q-q') == abs(p-p')
> queen n = csp queenconflict [(q, [1..n]) | q <- [1..n]]