### 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)I've also turned on the customzied printing of solutions (remove or comment out

(printout t ?question " No" crlf)

(return FALSE))

*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::queensI wrote a function to generate and assert var facts:

(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)))

)

(deffunction PROPAG::generate-var (?i $?v)there's also a matching rule:

(assert (var (name (sym-cat x ?i)) (possible-values $?v))))

(defrule generate-varsand the deffacts becomes:

(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)))

(deffacts PROPAG::queensOk, 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.

(generate-vars))

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")I really have no idea if CCP is fast or slow but here are some numbers:

+%%%$!*****+******

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>

n | rules | secondsI'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.

---+-------+-------

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

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.

## 8 kommentarer:

Very interesting benchmarks :) Thanks for sharing this with the world.

Have you tried running Drools-solver's NQueensApp on the same machine? With subversion and maven2 installed, it easy and described in

the drools-solver manual.

There's also a class to generate unsolved NQueens instances.

I wonder what the results are on the same computer if you compare both. Drools solver's 64queens takes less then a minute on my machine.

Drools-solver NQueens implementation isn't optimized yet though, as it doesn't use a scalable selector yet. That feature potentially has a bigO impact (=> a lot better scalability), but it will be interesting to see the current implementations battle already too.

Also note that drools-solver really starts to shine when you start adding in extra constraints (NQueens only has 3).

What algorithm does the clips implementation use? Is it brute force, branch-and-bound, ...?

Hi Geoffrey,

I wonder what the results are on the same computer if you compare both.My initial intent was actually to benchmark against your code but I soon realised that it would be nearly pointless since I know too little about the algorithms used, I'm not really sure what I'm comparing. Also, Drools' solver is implemented in Java right? The "engine" is not a bunch of rules, like in CCP? That difference alone I assume will make up for much of the run-time difference.

Anyway, I ran CCP with n = 64 and it took nearly 38 minutes to find the first solution.

What algorithm does the clips implementation use? Is it brute force, branch-and-bound, ...?Honestly, I'm not very familiar with their research, I've read the paper but that's about it. And when I studied the code I didn't spend too much time on the algorithm implementation as such. My interest was more regarding the "engine" and how they've packaged it for reuse.

I'll have a look though. It would be interesting to try and implement different heuristics for use in different situations.

Thanks for timing it :) I expect to get 64 queens down a lot more than under a minute with the upcoming refactors.

Drools solver's NQueens currently uses tabu search.

The drools rule engine is just used for score calculation (= implementing constraints like 2 queens cannot attack each other), not for traversing the search space.

To make sure these numbers are fair, it might be interesting to run clips and drools-solver's nqueens implementation for 62, 64 and 66 queens on the same computer. An unlucky start can easily result in a really bad benchmark time.

I expect to get 64 queens down a lot more than under a minute ...Ok, well. I think that kind of performance is going to be very difficult to obtain since the driver loop has to go through the whole match-resolve-act cycle. I wonder how fast it would be if the engine was implemented as a function instead. I just may have to try that... so much fun stuff to do, so little time :-)

Drools solver's NQueens currently uses tabu search.I think the "full" name for CCP's algorithm is: Chronological backtracking with forward checking.

It selects a variable as it's starting point, selects a value from that variable's solution space and then removes that value from the other variables' solution spaces (that's the forward checking part). It backtracks if it finds that a variable has no possible values left in it's solution space.

An unlucky start can easily result in a really bad benchmark time.Do you have the same sort of situation with Drools solver that a solution with a larger n, say 20, is "easier" (or at least faster) to find than a solution for, say n = 16?

BTW, did you ever get around to try out Drools solver for either of the Drools Puzzles?

An unlucky start can easily result in a really bad benchmark time.

Do you have the same sort of situation with Drools solver that a solution with a larger n, say 20, is "easier" (or at least faster) to find than a solution for, say n = 16?

Yes, for example 8 queens takes more steps than 16 queens (which is not logical), probably because it encounters more local optima. 16 queens does still take longer though because a step takes longer.

BTW, did you ever get around to try out Drools solver for either of the Drools Puzzles?Yes, for the second puzzle, but that was really really overkill.

It had like 36 possible solutions.

64 queens has over 3e115 possible solutions (= a 3 with 115 zero's behind it), which is still a joke compare to the examination problem size (see manual).

It had like 36 possible solutions.Really? I was under the impression there was only one. But then again, I used a brute-force generate-and-test approach and stopped once I had found a solution so I don't really know...

Any idea of how much faster your solution was?

Only 1 feasible/optimal solution, but 36 possible solutions.

Ok, I see what you mean... sorry, I'm a bit slow sometimes ;-)

Anyway, I'll try to improve the run-time of CCP and N-Queens and run some more benchmarks. I'll get back to you...

Skicka en kommentar