csp

Discrete constraint satisfaction problem (CSP) solver.

Version on this page:1.4.0
LTS Haskell 12.24:1.4.0
Stackage Nightly 2018-12-19:1.4.0
Latest on Hackage:1.4.0

See all snapshots csp appears in

LGPL licensed and maintained by Andrei Barbu

Module documentation for 1.4.0

There are no documented modules for this package.

CSP

Build Status

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
import Control.Monad.CSP

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
Depends on 4 packages:
Used by 1 package:
comments powered byDisqus