You are looking at historical revision 39572 of this page. It may differ significantly from its current revision.

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

This page is maintained in the package's github repository.

CSP

This is a Chicken Scheme egg which solves constraint satisfaction problems.

A CSP is composed of a number of domain-variables that have a domain, a set of bindings they can assume, along with a number of constraints. This egg supports 5 kinds of constraints: efd (early failure detection), fc (forward checking), vp (value propagation), gfc (generalized forward checking) and ac (arc consistency).

High-level

[procedure] (csp-solution domain-variables select)

Given a list of domain variables and a function to select which one to try to bind next, one can simply pass in first, this produces a solution to the CSP.

[procedure] (create-domain-variable domain)

Create a domain variable whose domain is domain.

[parameter] *csp-strategy*
[procedure] (assert-constraint! constraint domain-variables)

Assert a constraint, a function that returns a boolean, between a number of domain variables. The kind of constraint is determined by inspecting *csp-strategy*. Valid types are: efd (early failure detection), fc (forward checking), vp (value propagation), gfc (generalized forward checking) and ac (arc consistency). The default is ac. For constraints of low arity, a small number of domain variables, it will use an optimized version of the constraint propagation code.

[procedure] (bound? domain-variable)
[procedure] (binding domain-variable)

Determine if the domain variable is bound and what its binding is.

Constraints

[procedure] (assert-unary-constraint-efd! constraint x)
[procedure] (assert-binary-constraint-efd! constraint x y)
[procedure] (assert-ternary-constraint-efd! constraint x y z)
[procedure] (assert-unary-constraint-fc! constraint x)
[procedure] (assert-binary-constraint-fc! constraint x y)
[procedure] (assert-ternary-constraint-fc! constraint x y z)
[procedure] (assert-unary-constraint-vp! constraint x)
[procedure] (assert-binary-constraint-vp! constraint x y)
[procedure] (assert-ternary-constraint-vp! constraint x y z)
[procedure] (assert-unary-constraint-gfc! constraint x)
[procedure] (assert-binary-constraint-gfc! constraint x y)
[procedure] (assert-ternary-constraint-gfc! constraint x y z)
[procedure] (assert-unary-constraint-ac! constraint x)
[procedure] (assert-binary-constraint-ac! constraint x y)
[procedure] (assert-ternary-constraint-ac! constraint x y z)

Assert each of the 5 kinds of constraints between domain-variables x, y and z. You can always use assert-constraint! instead and it will default to these functions if your constraint is of low arity.

[procedure] (assert-constraint-efd! constraint ds)
[procedure] (assert-constraint-fc! constraint ds)
[procedure] (assert-constraint-vp! constraint ds)
[procedure] (assert-constraint-gfc! constraint ds)
[procedure] (assert-constraint-ac! constraint ds)

Assert each of the 5 kinds of constraints between the list of domain-variables ds. You can always use assert-constraint! instead as it will pick an optimized version for each of the above if the arity of the constraint is low.

Low-level

[procedure] (attach-before-demon! demon x)
[procedure] (attach-after-demon! demon x)
[procedure] (restrict-domain! x domain)

Only of interest to implementers.

Examples

This solves Project Euler problem 43.

 (use traversal nondeterminism csp)
 (let* ((ds (map-n (lambda _ (create-domain-variable (map-n identity 10))) 10))
 	(d3 (lambda (ns) (+ (* (first ns) 100) (* (second ns) 10) (third ns))))
 	(div (lambda (n) (lambda ns (= (modulo (d3 ns) n) 0))))
 	(nthd (lambda (a b) (sublist ds (- a 1) b))))
   (assert-constraint! (div 17) (nthd 8 10))
   (assert-constraint! (div 13) (nthd 7 9))
   (assert-constraint! (div 11) (nthd 6 8))
   (assert-constraint! (div 7) (nthd 5 7))
   (assert-constraint! (div 5) (nthd 4 6))
   (assert-constraint! (div 3) (nthd 3 5))
   (assert-constraint! (div 2) (nthd 2 4))
   (map-all-pairs (lambda l (assert-constraint! (lambda (a b) (not (= a b))) l)) ds)
   (foldl + 0
          (map (lambda (l) (foldl (lambda (a b) (+ (* a 10) b)) 0 l))
               (all-values (csp-solution ds last)))))

License

 
  Copyright 1993-1995 University of Toronto. All rights reserved.
  Copyright 1996 Technion. All rights reserved.
  Copyright 1996 and 1997 University of Vermont. All rights reserved.
  Copyright 1997-2001 NEC Research Institute, Inc. All rights reserved.
  Copyright 2002-2013 Purdue University. All rights reserved.
  Contact Andrei Barbu, andrei@0xab.com. Originally written by Jeff Siskind.
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.
  You should have received a copy of the GNU Lesser General Public License
  along with this program.  If not, see http://www.gnu.org/licenses.