csp: Discrete constraint satisfaction problem (CSP) solver.

[ ai, constraints, control, failure, library, monads ] [ Propose Tags ]

Constraint satisfaction problem (CSP) solvers

Versions [RSS] [faq] 1.0, 1.3, 1.3.1, 1.4.0 base (>=3 && <5), containers, mtl (>=2), nondeterminism (>=1.4) [details] LicenseRef-LGPL Andrei Barbu Andrei Barbu Control, AI, Constraints, Failure, Monads head: git clone http://github.com/abarbu/csp-haskell by AndreiBarbu at 2018-03-14T13:37:28Z LTSHaskell:1.4.0, NixOS:1.4.0, Stackage:1.4.0 3306 total (18 in the last 30 days) 2.0 (votes: 1) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2018-03-14

Modules

[Index]

Maintainer's Corner

For package maintainers and hackage trustees

Candidates

• No Candidates

[back to package description]

CSP

This package is available via Hackage where its documentation resides. It provides a solver for constraint satisfaction problems by implementing a CSP monad. Currently it only implements arc consistency but other kinds of constraints will be added.

Below is a Sudoku solver, project Euler problem 96.

import Data.List

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

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]]

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


Future

• Allow a randomized execution order for CSPs
• CSPs don't need to use IO internally. ST is enough.
• Constraint synthesis. Already facilitated by the fact that constraints are internally nondeterministic
• Other constraint types for CSPs, right now only AC is implemented
• n-ary heterogeneous constraints