Safe Haskell  None 

Language  Haskell2010 
 mkDV :: [a] > CSP r (DV r a)
 constraint1 :: (a > Bool) > DV r1 a > CSP r ()
 constraint2 :: (a > t1 > Bool) > DV t a > DV t t1 > CSP r ()
 constraint :: ([a] > Bool) > [DV r1 a] > CSP r ()
 oneCSPSolution :: CSPResult a1 => CSP (Result a1) a1 > Result a1
 allCSPSolutions :: CSPResult a1 => CSP (Result a1) a1 > [Result a1]
 solveCSP :: CSPResult a1 => (AmbT r IO (Result a1) > IO a) > CSP r a1 > a
 class CSPResult a where
 csp :: IO x > CSP r x
 domain :: DV t t1 > IO [t1]
 demons :: DV r a > IO [Constraint r]
 isBound :: DV t t1 > IO Bool
 domainSize :: DV t t1 > IO Int
 localWriteIORef :: IORef a > a > AmbT r IO ()
 binding :: DV t b > IO b
 addConstraint :: DV r1 a > Constraint r1 > CSP r ()
 restrictDomain :: DV r a > ([a] > IO [a]) > AmbT r IO ()
 data DV r a = DV {
 dvDomain :: IORef [a]
 dvConstraints :: IORef [Constraint r]
 data DVContainer r = DVContainer {
 dvcIsBound :: AmbT r IO Bool
 dvcConstraints :: AmbT r IO ()
 dvcABinding :: AmbT r IO ()
 type Constraint r = AmbT r IO ()
 data CSP r x = CSP {
 unCSP :: IORef [DVContainer r] > IO x
Overview
This constructs a discrete constraint satisfaction problem (CSP) and then solves it. A discrete CSP consists of a number of variables each having a discrete domain along with a number of constraints between those variables. Solving a CSP searches for assignments to the variables which satisfy those constraints. At the moment the only constraint propagation technique available is arc consistency.
Here is a simple example which solves Sudoku puzzles, project Euler problem 96.
import Data.List import Control.Monad.CSP solveSudoku :: (Enum a, Eq a, Num a) => [[a]] > [[a]] solveSudoku puzzle = oneCSPSolution $ do dvs < mapM (mapM (\a > mkDV $ if a == 0 then [1 .. 9] else [a])) puzzle mapM_ assertRowConstraints dvs mapM_ assertRowConstraints $ transpose dvs sequence_ [assertSquareConstraints dvs x y  x < [0,3,6], y < [0,3,6]] return dvs where assertRowConstraints = mapAllPairsM_ (constraint2 (/=)) assertSquareConstraints dvs i j = mapAllPairsM_ (constraint2 (/=)) [(dvs !! x) !! y  x < [i..i+2], y < [j..j+2]] mapAllPairsM_ :: Monad m => (a > a > m b) > [a] > m () mapAllPairsM_ f [] = return () mapAllPairsM_ f (_:[]) = return () mapAllPairsM_ f (a:l) = mapM_ (f a) l >> mapAllPairsM_ f l sudoku3 = [[0,0,0,0,0,0,9,0,7], [0,0,0,4,2,0,1,8,0], [0,0,0,7,0,5,0,2,6], [1,0,0,9,0,4,0,0,0], [0,5,0,0,0,0,0,4,0], [0,0,0,5,0,7,0,0,9], [9,2,0,1,0,8,0,0,0], [0,3,4,0,5,9,0,0,0], [5,0,7,0,0,0,0,0,0]]
>>>
solveSudoku sudoku3
[[4,6,2,8,3,1,9,5,7],[7,9,5,4,2,6,1,8,3],[3,8,1,7,9,5,4,2,6],[1,7,3,9,8,4,2,6,5],[6,5,9,3,1,2,7,4,8],[2,4,8,5,6,7,3,1,9],[9,2,6,1,7,8,5,3,4],[8,3,4,2,5,9,6,7,1],[5,1,7,6,4,3,8,9,2]]
Building CSPs
constraint1 :: (a > Bool) > DV r1 a > CSP r () Source
Assert a unary constraint.
constraint2 :: (a > t1 > Bool) > DV t a > DV t t1 > CSP r () Source
Assert a binary constraint with arc consistency.
constraint :: ([a] > Bool) > [DV r1 a] > CSP r () Source
Assert an nary constraint with arc consistency. One day this will allow for a heterogeneous list of variables, but at the moment they must all be of the same type.
Solving CSPs
allCSPSolutions :: CSPResult a1 => CSP (Result a1) a1 > [Result a1] Source
Return all solutions to the CSP. solveCSP
running with
allValuesT
solveCSP :: CSPResult a1 => (AmbT r IO (Result a1) > IO a) > CSP r a1 > a Source
Solve the given CSP. The CSP solver is a nondeterministic function in IO and this is the generic interface which specifies how the nondeterministic computation should be carried out.
Lowlevel internal
Lift an IO computation into the CSP monad. CSPs are only in IO temporarily.
demons :: DV r a > IO [Constraint r] Source
Extract the current constraints of a variable.
domainSize :: DV t t1 > IO Int Source
Compute the size of the current domain of variable.
localWriteIORef :: IORef a > a > AmbT r IO () Source
This performs a sideeffect, writing to the given IORef but records this in the nondeterministic computation so that it can be undone when backtracking.
addConstraint :: DV r1 a > Constraint r1 > CSP r () Source
Add a constraint to the given variable.
restrictDomain :: DV r a > ([a] > IO [a]) > AmbT r IO () Source
The lowlevel function out of which constraints are constructed. It modifies the domain of a variable.
Types
DV  

data DVContainer r Source
DVContainer  

type Constraint r = AmbT r IO () Source