((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/csp" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (tags "egg" "data") (toc) (p "This page is maintained in the package's " (link "https://github.com/abarbu/csp" "github repository") ".")) (section 2 "CSP" (p "This is a Chicken Scheme egg which solves constraint satisfaction problems.") (p "A CSP is composed of a number of " (i "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: " (i "efd") " (early failure detection), " (i "fc") " (forward checking), " (i "vp") " (value propagation), " (i "gfc") " (generalized forward checking) and " (i "ac") " (arc consistency).") (section 4 "High-level" (def (sig (procedure "(csp-solution domain-variables select)" (id csp-solution))) (p "Given a list of domain variables and a function to select which one to try to bind next, one can simply pass in " (i "first") ", this produces a solution to the CSP.")) (def (sig (procedure "(create-domain-variable domain)" (id create-domain-variable))) (p "Create a domain variable whose domain is " (i "domain") ".")) (def (sig (parameter "*csp-strategy*" (id *csp-strategy*)) (procedure "(assert-constraint! constraint domain-variables)" (id assert-constraint!))) (p "Assert a constraint, a function that returns a boolean, between a number of domain variables. The kind of constraint is determined by inspecting " (i "*csp-strategy*") ". Valid types are: " (i "efd") " (early failure detection), " (i "fc") " (forward checking), " (i "vp") " (value propagation), " (i "gfc") " (generalized forward checking) and " (i "ac") " (arc consistency). The default is " (i "ac") ". For constraints of low arity, a small number of domain variables, it will use an optimized version of the constraint propagation code.")) (def (sig (procedure "(bound? domain-variable)" (id bound?)) (procedure "(binding domain-variable)" (id binding))) (p "Determine if the domain variable is bound and what its binding is."))) (section 4 "Constraints" (def (sig (procedure "(assert-unary-constraint-efd! constraint x)" (id assert-unary-constraint-efd!)) (procedure "(assert-binary-constraint-efd! constraint x y)" (id assert-binary-constraint-efd!)) (procedure "(assert-ternary-constraint-efd! constraint x y z)" (id assert-ternary-constraint-efd!)) (procedure "(assert-unary-constraint-fc! constraint x)" (id assert-unary-constraint-fc!)) (procedure "(assert-binary-constraint-fc! constraint x y)" (id assert-binary-constraint-fc!)) (procedure "(assert-ternary-constraint-fc! constraint x y z)" (id assert-ternary-constraint-fc!)) (procedure "(assert-unary-constraint-vp! constraint x)" (id assert-unary-constraint-vp!)) (procedure "(assert-binary-constraint-vp! constraint x y)" (id assert-binary-constraint-vp!)) (procedure "(assert-ternary-constraint-vp! constraint x y z)" (id assert-ternary-constraint-vp!)) (procedure "(assert-unary-constraint-gfc! constraint x)" (id assert-unary-constraint-gfc!)) (procedure "(assert-binary-constraint-gfc! constraint x y)" (id assert-binary-constraint-gfc!)) (procedure "(assert-ternary-constraint-gfc! constraint x y z)" (id assert-ternary-constraint-gfc!)) (procedure "(assert-unary-constraint-ac! constraint x)" (id assert-unary-constraint-ac!)) (procedure "(assert-binary-constraint-ac! constraint x y)" (id assert-binary-constraint-ac!)) (procedure "(assert-ternary-constraint-ac! constraint x y z)" (id assert-ternary-constraint-ac!))) (p "Assert each of the 5 kinds of constraints between domain-variables " (i "x") ", " (i "y") " and " (i "z") ". You can always use " (i "assert-constraint!") " instead and it will default to these functions if your constraint is of low arity.")) (def (sig (procedure "(assert-constraint-efd! constraint ds)" (id assert-constraint-efd!)) (procedure "(assert-constraint-fc! constraint ds)" (id assert-constraint-fc!)) (procedure "(assert-constraint-vp! constraint ds)" (id assert-constraint-vp!)) (procedure "(assert-constraint-gfc! constraint ds)" (id assert-constraint-gfc!)) (procedure "(assert-constraint-ac! constraint ds)" (id assert-constraint-ac!))) (p "Assert each of the 5 kinds of constraints between the list of domain-variables ds. You can always use " (i "assert-constraint!") " instead as it will pick an optimized version for each of the above if the arity of the constraint is low."))) (section 4 "Low-level" (def (sig (procedure "(attach-before-demon! demon x)" (id attach-before-demon!)) (procedure "(attach-after-demon! demon x)" (id attach-after-demon!)) (procedure "(restrict-domain! x domain)" (id restrict-domain!))) (p "Only of interest to implementers."))) (section 3 "Examples" (p "This solves " (link "http://projecteuler.net/problem=43" "Project Euler problem 43") ".") (pre " (use traversal nondeterminism csp)\n (let* ((ds (map-n (lambda _ (create-domain-variable (map-n identity 10))) 10))\n \t(d3 (lambda (ns) (+ (* (first ns) 100) (* (second ns) 10) (third ns))))\n \t(div (lambda (n) (lambda ns (= (modulo (d3 ns) n) 0))))\n \t(nthd (lambda (a b) (sublist ds (- a 1) b))))\n   (assert-constraint! (div 17) (nthd 8 10))\n   (assert-constraint! (div 13) (nthd 7 9))\n   (assert-constraint! (div 11) (nthd 6 8))\n   (assert-constraint! (div 7) (nthd 5 7))\n   (assert-constraint! (div 5) (nthd 4 6))\n   (assert-constraint! (div 3) (nthd 3 5))\n   (assert-constraint! (div 2) (nthd 2 4))\n   (map-all-pairs (lambda l (assert-constraint! (lambda (a b) (not (= a b))) l)) ds)\n   (foldl + 0\n          (map (lambda (l) (foldl (lambda (a b) (+ (* a 10) b)) 0 l))\n               (all-values (csp-solution ds last)))))")) (section 3 "License" (pre "  Copyright 1993-1995 University of Toronto. All rights reserved.\n  Copyright 1996 Technion. All rights reserved.\n  Copyright 1996 and 1997 University of Vermont. All rights reserved.\n  Copyright 1997-2001 NEC Research Institute, Inc. All rights reserved.\n  Copyright 2002-2013 Purdue University. All rights reserved.") (pre "  Contact Andrei Barbu, andrei@0xab.com. Originally written by Jeff Siskind.") (pre "  This program is free software: you can redistribute it and/or modify\n  it under the terms of the GNU Lesser General Public License as published by\n  the Free Software Foundation, either version 3 of the License, or\n  (at your option) any later version.\n  This program is distributed in the hope that it will be useful,\n  but WITHOUT ANY WARRANTY; without even the implied warranty of\n  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n  GNU Lesser General Public License for more details.\n  You should have received a copy of the GNU Lesser General Public License\n  along with this program.  If not, see http://www.gnu.org/licenses."))))