[Python-logic] Constraint, modelling, solving and all that...

[Alexandre]

From: Arnold Maestre <maestre at lirmm.fr>
X-Mailer: Evolution 2.0.2 
X-Spambayes-Classification: ham; 0.00
To: nico at logilab.fr, alf at logilab.fr
Date: Sat, 13 Nov 2004 03:39:21 +0100
Subject: Constraint, modelling, solving and all that...

Hi,

I wanted to get my feet wet with your constraint library, so I gave it a
try and coded a simple problem: the knight's tour problem. It's a well
known board game, where you have to place the n^2 first numbers on a n*n
chessboard, so that each number is a knight's move away from its
predecessor and from its successor.

I attached the file, feel free to add it to your set of examples if my
nascent python syntax doesn't scare you.

The model is straightforward and includes some basic knowledge of the
problem: odd steps are black, even steps are white (so the domains are
cut in half), actually if I was not so lazy I would have cut the domain
of the first variable down to a quarter chessboard, because of axial
symetries, I might as well add a basic constraint next time...
(Edit: I stopped being lazy, added the unary constraint, and it actually

Using the library is a breeze, I really liked it. Being able to design a
constraint just by stating a python expression is sweet, even though it
might (and will) blow your head off if you design a non-trivial test...
The same goes for the domains, suing tuples was so much easier than
fiddling with Z/nZ, but I wonder if it's not too big a hit in terms of
performance.

Because that's the nasty part: performance... On my computer, the
simplest knight's tour (size 5, non re-entrant) took 26 seconds to
compute... I didn't bother trying larger problems, this toy-problem is
usually considered as a basis for refinements (like: make a tour and
place a queen on the chessboard so that she can reach any prime number
in one move, or make a tour so that the board is a magic square,
etc...). The model can be enhanced, but still, 26 seconds...

So I took a look at the code, and found this: 

def distribute(self, distributor, verbose=0):
    return [Repository(self._variables, domain, self._constraints) 
        for domain in distributor.distribute(self._domains, verbose)]

I don't know python so well, so I may hust as well miss the mark, but it
looks like the distributor makes a complete copy of the problem. If this
is not the case, pardon my incompetence, else, look no further: in the
worst case, we're talking about creating/copying 25 variables, their
domains and their constraints just for one step in the search on a very
small problem. And then destroy all that when you backtrack...

I didn't have time to check the propagation, but it also looks like
you're doing *way* too much work there. Entailing the constraint means
d^2 constraint checks each time you give it a shot, but to make the
constraint arc-consistent, you just need to find one support for each
value on the opposite domain. Moreover, why bother checking entailment:
you will reduce the domain to one value at some point, and then the
constraint will be entailed... Once you have a support (a compatible
value), you don't need to check the rest of the domain, you can benefit
from the hard work in three ways. First, tell your "support" that if he
dies, you're not supported anymore ("support" has a list of values that
must be revised if he's deleted). Second, remeber that you've checked
the opposite domain up to "support". If he dies, you just need to check
the remainder of the domain, you already know that there's nothing for
you in the beginning. Third, guess what ? If he's your buddy, you're his
buddy too, so if ever he needs he needs a support, he knows he can count
on you without checking. The key idea being "you should never need to do
the same check twice".

I can provide more details and pointers to relevant papers if you need
any, but if I'm not mistaken, our biggest FIXME here is the distributor.
Let me know if I missed something.
--
Arnold Maestre

PS: I'm not sure this discussion belongs to the python-logic list, you
can forward it there if you feel like. By the way, I'm french, so you
can use french if you reply in private.