screamer
Screamer is a language extension that adds support for nondeterministic programming, including backtracking and undoable side-effects, and includes a constraint programming language.

Screamer was originally written by Jeffrey Mark Siskind and David Allen McAllester, and released under an non-DFSG-free "old school" license in 1991. It has since then been released with permission under at least GPL and MIT-licenses.

Probably the most alive version of Screamer is an MIT-licensed copy on Github, which should run on any ANSI Common Lisp and can be installed using Quicklisp.


The following Screamer code finds a 3x3 matrix of the integers between 1 and 9, such that the sums of the verticals, horizontals, and diagonals are equal.

(defun 3X3 ()
  (let ((a (an-integer-betweenv 1 9))
        (b (an-integer-betweenv 1 9))
        (c (an-integer-betweenv 1 9))
        (d (an-integer-betweenv 1 9))
        (e (an-integer-betweenv 1 9))
        (f (an-integer-betweenv 1 9))
        (g (an-integer-betweenv 1 9))
        (h (an-integer-betweenv 1 9))
        (i (an-integer-betweenv 1 9)))
    ;; make sure they all different
    (assert! (/=v a b c d e f g h i))

    ;; make sure the various directions add up
    (assert! (=v (+v a b c) (+v d e f) (+v g h i)
                 (+v a d g) (+v b e h) (+v c f i)
                 (+v a e i) (+v c e g)))
    (apply #'format (append (list t "Solution: ~%~d ~d ~d~%~d ~d ~d~%~d ~d ~d")
                            (one-value (solution (list a b c d e f g h i)
                                                 (static-ordering #'linear-force)))))))

SCREAMER-USER 4 > (3X3)
Solution: 
2 7 6
9 5 1
4 3 8
NIL

There is also an extension to Screamer, called Screamer+, described in the paper Constraint Handling in Common LISP. A copy of the source code that "may be used cost-free for non-commercial use" can be found here (Broken link, as of 11/2010, mirror here.)


Notes

Install

Buried at the bottom of screamer/README, it says you need a certain "preamble" at the top of a file in which you use it. Something like:

(IN-PACKAGE :CL-USER)
(SCREAMER:DEFINE-SCREAMER-PACKAGE :MY-PACKAGE
  ;; ...optional defpackage arguments...
  )
(IN-PACKAGE :MY-PACKAGE)

Trace weirdness

I could be somehow mistaken, but it seems that TRACEing a nondeterministic function (Screamer seems to replace normal DEFUN with its own) may not be completely reliable. Here's something from my code where I don't expect SOLVE-ONCE's trace to show that it returns different things:

(in-package :cl-user)
(screamer:define-screamer-package :blah
    (:export :solve-once
             :with-indices
             :eltv
             :mid))
(in-package :blah)

;;; Utilities

(defun solve-once (&rest things)
  (one-value (solution things (static-ordering #'linear-force))))

(defmacro with-indices (indices &body body)
  `(let* ,(loop with last-index = (1- (length indices))
                for i in indices
                collect `(,i (an-integer-betweenv 0 ,last-index)))
    (assert! (/=v ,@indices))
    ,@body))

(defun eltv (&rest rest)
  (applyv #'elt rest))

;;; Example

(defun mid (n1 n2 n3)
  (let ((numbers (vector n1 n2 n3)))
    (with-indices (min mid max)
      (assert! (<=v (eltv numbers min)
                    (eltv numbers mid)
                    (eltv numbers max)))
      (elt numbers (first (solve-once mid min max))))))


(trace solve-once)

(mid 0 1 2)
;; Trace:
;;  0: (SOLVE-ONCE [1168 integer 0:2 enumerated-domain: (0 1 2)]
;;                 [1165 integer 0:2 enumerated-domain: (0 1 2)]
;;                 [1171 integer 0:2 enumerated-domain: (0 1 2)])
;;  0: SOLVE-ONCE returned (1 0 2)

(mid 1 2 0)
;; Trace:
;;  0: (SOLVE-ONCE [1180 integer 0:2 enumerated-domain: (0 1 2)]
;;                 [1177 integer 0:2 enumerated-domain: (0 1 2)]
;;                 [1183 integer 0:2 enumerated-domain: (0 1 2)])
;;  0: SOLVE-ONCE returned (0 2 1)


Topics: pattern matching