Constraint Programming in Clips

A couple of weeks ago, I found Michel Futtersack and Jean Marc Labat's research on Constraint Programming in Clips from 1997. I've spent part of Christmas going through the source code. It's quite an interesting "read" if you're a Clips user. They've implemented a backtracking search algorithm with forward checking. But the really cool thing is that they've packaged it all as a reusable component (in CCP.clp) to be used as the main driver to find solutions for any Constraint Satisfaction Problem (CSP).

They've also provided some examples, one of them is the classic N-Queens. But I've modified it a bit to make it easier to try out different sizes of the chessboard. Also, their implementation is based around either finding all solutions to a problem or finding solutions one by one until the user says stop. This makes it a bit difficult to time the algorithm and compare it against, for example, Drools' solver module. What I want it to do is to find the first solution and then quit, without any user interaction.

So here's what I changed:

The first question the main driver loop asks is: "Do you want all solutions?" and if you answer "No" the next question is "Do you want another solution?" So I can easily get what I want by short-circuiting the yes-or-no-p function in CCP.clp to always return FALSE (No).

(deffunction MAIN::yes-or-no-p (?question)
(printout t ?question " No" crlf)
(return FALSE))

I've also turned on the customzied printing of solutions (remove or comment out print-solution and remove the comments from to_customized_printing) because it's easier to read the result in that form.

When it comes to the specifics of the N-Queens problem (in n-queens.clp) they've put the definition of the solution space in two different deffacts: queens and chessboard, which unfortunately also binds the n implicitly.

For example, instead of having:

(deffacts PROPAG::queens
(var (name x1)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x2)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x3)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x4)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x5)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x6)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x7)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x8)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x9)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x10) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x11) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x12) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
)

I wrote a function to generate and assert var facts:

(deffunction PROPAG::generate-var (?i $?v)
(assert (var (name (sym-cat x ?i)) (possible-values $?v))))

there's also a matching rule:

(defrule generate-vars
(generate-vars)
(problem-size ?n)
=>
(loop-for-count (?i ?n)
(bind ?v (create$))
(loop-for-count (?j ?n)
   (bind ?v (insert$ $?v (+ (length$ $?v) 1) ?j)))
(generate-var ?i $?v)))

and the deffacts becomes:

(deffacts PROPAG::queens
(generate-vars))

Ok, maybe it's not the prettiest solution, but it gets the job done and I don't have to manually define 64, 128 or 256 var facts containing 64, 128 or 256 items long multislots. There's also similarly a function, a rule and a deffacts for the chessboard facts.

The problem size (marked with red above) is now instead specified in an implied deftemplate which is injected at the batch file level. So an N-Queens of size 12 can look like this:

CLIPS> (load "CCP.clp")
+%%%$!*****+******
TRUE
CLIPS> (load "n-queens.clp")
+$!%$!!*******
TRUE
CLIPS> (deffacts PROPAG::problem-size
(problem-size 12))
CLIPS> (watch statistics)
CLIPS> (reset)
CLIPS> (run)
Do you want all the solutions ?  No
the problem is solved
Do you want another solution ?  No
No more solution

I found 1 solution(s)



* * * * * * X * * * * *
* * * * * * * * X * * *
* * * * * * * * * * X *
* * * * X * * * * * * *
* X * * * * * * * * * *
* * * X * * * * * * * *
* * * * * * * * * * * X
* * * * * * * * * X * *
* * * * * * * X * * * *
* * * * * X * * * * * *
X * * * * * * * * * * *
* * X * * * * * * * * *


2181 rules fired        Run time is 1.101 seconds.
1980.92643051771 rules per second.
99 mean number of facts (116 maximum).
1 mean number of instances (1 maximum).
5 mean number of activations (23 maximum).
CLIPS>

I really have no idea if CCP is fast or slow but here are some numbers:

 n | rules | seconds
---+-------+-------
04 |    31 | 000.01
06 |   101 | 000.02
08 |   162 | 000.04
10 |   577 | 000.18
12 |  2181 | 001.06
16 |  2584 | 002.97
20 |   613 | 001.05
24 |  2709 | 012.95
28 |   699 | 002.89
32 |  9284 | 130.72

I'm guessing it's the heuristics of the forward checking (or possibly the structure of the problem) that makes the number of rules fired and the run-time to differ so much between different sizes of the chessboard. I was really expecting n = 28 to be "harder" than n = 24 but... apparently not.

If you also want to experiment with N-Queens in CCP, the modified files can be found here (CCP.clp), here (n-queens.clp) and here (n-queens.bat). They won't work with Clips 6.30 (Beta) though because of a problem with Logical CE's but I think Gary's on top of that already. Once a new release is out it will be interesting to see if the new and improved Rete implementation of Clips 6.3 will reduce the run-time and/or possibly the number of rules fired as well.