chickadee » csp

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

csp-solution domain-variables selectprocedure

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.

create-domain-variable domainprocedure

Create a domain variable whose domain is domain.

*csp-strategy*parameter
assert-constraint! constraint domain-variablesprocedure

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.

bound? domain-variableprocedure
binding domain-variableprocedure

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

Constraints

assert-unary-constraint-efd! constraint xprocedure
assert-binary-constraint-efd! constraint x yprocedure
assert-ternary-constraint-efd! constraint x y zprocedure
assert-unary-constraint-fc! constraint xprocedure
assert-binary-constraint-fc! constraint x yprocedure
assert-ternary-constraint-fc! constraint x y zprocedure
assert-unary-constraint-vp! constraint xprocedure
assert-binary-constraint-vp! constraint x yprocedure
assert-ternary-constraint-vp! constraint x y zprocedure
assert-unary-constraint-gfc! constraint xprocedure
assert-binary-constraint-gfc! constraint x yprocedure
assert-ternary-constraint-gfc! constraint x y zprocedure
assert-unary-constraint-ac! constraint xprocedure
assert-binary-constraint-ac! constraint x yprocedure
assert-ternary-constraint-ac! constraint x y zprocedure

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.

assert-constraint-efd! constraint dsprocedure
assert-constraint-fc! constraint dsprocedure
assert-constraint-vp! constraint dsprocedure
assert-constraint-gfc! constraint dsprocedure
assert-constraint-ac! constraint dsprocedure

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

attach-before-demon! demon xprocedure
attach-after-demon! demon xprocedure
restrict-domain! x domainprocedure

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.

Contents »