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-variable*s 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``select`procedureGiven 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``domain`procedureCreate a domain variable whose domain is

*domain*.

`*csp-strategy*`parameter`assert-constraint!``constraint``domain-variables`procedureAssert 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-variable`procedure`binding``domain-variable`procedureDetermine if the domain variable is bound and what its binding is.

#### Constraints

`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`procedureAssert 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``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`procedureAssert 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``x`procedure`attach-after-demon!``demon``x`procedure`restrict-domain!``x``domain`procedureOnly 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.