csp: Discrete constraint satisfaction problem (CSP) solvers.

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

Constraint satisfaction problem (CSP) solvers


[Skip to Readme]
Versions [faq] 1.0, 1.3, 1.3.1, 1.4.0
Dependencies base (>=3 && <5), containers, mtl (>=2), nondeterminism [details]
License LicenseRef-LGPL
Author Andrei Barbu <andrei@0xab.com>
Maintainer Andrei Barbu <andrei@0xab.com>
Category Control, AI, Constraints, Failure, Monads
Source repo head: git clone git://github.com/abarbu/csp-haskell.git
Uploaded by AndreiBarbu at Wed Aug 14 08:53:46 UTC 2013
Distributions LTSHaskell:1.4.0, NixOS:1.4.0, Stackage:1.4.0
Downloads 1669 total (46 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for csp-1.0

[back to package description]

CSP

A simple example which solves Sudoku puzzles, project Euler problem 96.

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

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 sudoku3

Future

  • Docs!
  • Allow a randomized execution order for CSPs
  • CSPs don't need 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