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 ()
 constraint3 :: (a > t1 > t2 > Bool) > DV t a > DV t t1 > DV t t2 > 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
 type Result a
 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
constraint2 :: (a > t1 > Bool) > DV t a > DV t t1 > CSP r () Source #
Assert a binary constraint with arc consistency.
constraint3 :: (a > t1 > t2 > Bool) > DV t a > DV t t1 > DV t t2 > CSP r () Source #
Assert a trinary 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.
class CSPResult a where Source #
This extracts results from a CSP.
CSPResult a => CSPResult [a] Source #  
(CSPResult a, CSPResult b) => CSPResult (a, b) Source #  
CSPResult (DV r a) Source #  
(CSPResult a, CSPResult b, CSPResult c) => CSPResult (a, b, c) Source #  
(CSPResult a, CSPResult b, CSPResult c, CSPResult d) => CSPResult (a, b, c, d) Source #  
(CSPResult a, CSPResult b, CSPResult c, CSPResult d, CSPResult e) => CSPResult (a, b, c, d, e) Source #  
(CSPResult a, CSPResult b, CSPResult c, CSPResult d, CSPResult e, CSPResult f) => CSPResult (a, b, c, d, e, f) Source #  
Lowlevel internal
csp :: IO x > CSP r x Source #
Lift an IO computation into the CSP monad. CSPs are only in IO temporarily.
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 #