Rosio Pavoris a blog

Alright, we’ve covered search trees in some detail, and they work great for problems where we have clear states and rules of production to move from one state to the next. Sometimes that’s not a very convenient way to state a problem, though, and a more natural way to think about things is as a bunch of variables which can take values in a certain domain, and a number of constraints which describe the relationships of these variables to each other.
The canonical example here is Dijkstra’s eight queens problem. However, that’s been done to death, so let’s instead have two queens and seven knights, and instead of the usual 8×8 chess board, let’s have a 6×6 one.

In case you aren’t familiar with the problem, the idea is to place all the pieces on the board in such a way that none of them threatens any other.
Clearly we have nine variables (two queens and seven knights), and the domain for each of them is any of the thirty-six positions on the board, represented as a tuple of numbers to indicate the row and column. In Python, we could represent this like this:

> domains = {'Q1': set([(a, b) for a in range(6) for b in range(6)]),
>            'Q2': set([(a, b) for a in range(6) for b in range(6)]),
>            'K1': set([(a, b) for a in range(6) for b in range(6)]),
>            'K2': set([(a, b) for a in range(6) for b in range(6)]),
>            'K3': set([(a, b) for a in range(6) for b in range(6)]),
>            'K4': set([(a, b) for a in range(6) for b in range(6)]),
>            'K5': set([(a, b) for a in range(6) for b in range(6)]),
>            'K6': set([(a, b) for a in range(6) for b in range(6)]),
>            'K7': set([(a, b) for a in range(6) for b in range(6)])}
> 
> pieces = set(domains.keys())
> queens = set(['Q1', 'Q2'])
> knights = pieces - queens

(Using sets not (primarily) because I’m worried there would be duplicate entries there, but because Python’s sets have some useful operations defined on them that lists don’t, as will become clear.)

Representing the constraints may be a bit trickier. We’ll only be working with arc constraints (that is, constraints that apply to exactly two variables), because that makes sense, and it turns out that higher-order constraints aren’t much more useful.⁰ Should you have any single-variable constraints, those can be applied directly to reduce the domains in advance, obviously.
There are a lot of ways to represent this, but I’m going to go with a class that stores the two variables the constraint applies to, plus a constraint function, which operates on two values from the domains of the variables and tells you whether the constraint is satisfied or not. The class also has a valid method, which just applies the constraint function.

> class Constraint():
>     def __init__(self, p1, p2, constr_fun):
>         self.p1, self.p2, self.constr_fun = p1, p2, constr_fun
> 
>     def valid(self, a, b):
>         return self.constr_fun(a, b)

Now for the constraint functions themselves. Remember, these functions take two values from two domains, and return False if the first piece threatens the second (because we’re looking for situations where that doesn’t happen), and True otherwise.
A queen threatens everything on her row, column and diagonals, so her function looks like this:

> def queen_cf(queen, other):
>     return abs(queen[0] - other[0]) != abs(queen[1] - other[1]) \
>        and queen[0] != other[0] \
>        and queen[1] != other[1]

The knight threatens everything two moves in the horizontal or vertical direction plus one in the orthogonal, so its function looks like this:

> def knight_cf(knight, other):
>     if other[0] in (knight[0] - 2, knight[0] + 2):
>         return other[1] not in (knight[1] - 1, knight[1] + 1)
> 
>     if other[1] in (knight[1] - 2, knight[1] + 2):
>         return other[0] not in (knight[0] - 1, knight[0] + 1)
> 
>     return True

(Does it matter that it ignores the limits of the board? Not really: there will never be a piece outside of the board, but it does no harm to look. Explicitly checking board limits isn’t going to save any time.)

Finally, an optional constraint. Consider the following two solutions to our problem:

These are equivalent in every way that matters, of course, but will be returned as different solutions by our algorithm as written. You might think this isn’t a big deal, but there are 2! × 7! identical variants of every possible solution, and there are (it turns out) twenty-two legitimate solutions; paring down 221,760 solutions to find the twenty-two unique ones would be a challenge in its own right.
So let’s enforce the constraint that the position of Q1 must be strictly less than that of Q2, for some unambiguous ordering of the board’s squares, and the same for any knights compared to knights with a higher index. This will ensure that each solution found is genuinely unique. Fortunately, Python makes this easy.

> def index_cf(low, high):
>     return low < high

(Notice that this also implies that no two pieces can ever occupy the same square; otherwise we’d have to introduce another constraint for that, or modify our knight function (the queen function already implies it).)

Building our list of constraints is then relatively straightforward.

> constraints = [Constraint(q, p, queen_cf) for q in queens \
>                                           for p in pieces - set([q])] \
>             + [Constraint(k, p, knight_cf) for k in knights \
>                                            for p in pieces - set([k])] \
>             + [Constraint("Q1", "Q2", index_cf)] \
>             + [Constraint(a, b, index_cf) for a in knights \
>                                           for b in filter(lambda n: n > a,
>                                                           knights)]

And hey, that last constraint function means we can pare down our domains already: Q1 will never be in the highest square, because if there’s a queen there, it will be Q2. Similarly, Q2 will never be in the lowest, and any given knight will never occupy six squares at the ends of the board. By pruning our domains now, we’ll reduce our potential search space from 36⁹ to 35² × 30⁷, which is a savings of over 76 trillion.¹
Since each constraint has the potential to prune the domains of the variables it affects, it makes sense to do this as a method of the Constraint class.

>     def prune_domains(self):
>         p1_domain, p2_domain = domains[self.p1], domains[self.p2]
>         p1_new_domain, p2_new_domain = set(), set()
>         
>         for v1 in p1_domain:
>             for v2 in p2_domain:
>                 if self.constr_fun(v1, v2):
>                     p1_new_domain |= set([v1])
>                     p2_new_domain |= set([v2])
> 
>         deleted = len(p1_domain) != len(p1_new_domain) or \
>                   len(p2_domain) != len(p2_new_domain)
> 
>         return {self.p1: p1_new_domain, self.p2: p2_new_domain}, deleted

Just having each constraint prune once isn’t enough of course, because one constraint’s pruning may have repercussions for the pruning of another. The naïve way to deal with this would just be to keep letting all constraints prune until the domains don’t change anymore. This is a valid way of doing things, and known as the AC-1 algorithm (for Arc Consistency).
Smarter might be to have a queue of all constraints, remove one, have it prune, and if it affects the domain, add all constraints involving the variables of the affected domains that aren’t already in the queue to the queue; repeat until the queue is empty. That one is AC-3. (Both are courtesy of Alan Mackworth, incidentally).
It doesn’t matter a huge deal which we use; because we don’t have an easy way of getting the constraints on a given variable, AC-3 is going to be slower than it has to be, to the point where it might even be slower than AC-1. We could deal with this, but it’s not worth it. Let’s just do something.

> def ac3():
>     queue = constraints[:]
> 
>     while len(queue) > 0:
>         c = queue[0]
> 
>         new_domains, d = c.prune_domains()
>         domains.update(new_domains)
> 
>         if d:
>             new_constraints = []
>         
>             for con in constraints:
>                 if (con.p1 == c.p1 or con.p2 == c.p1 or \
>                     con.p1 == c.p2 or con.p2 == c.p2) and con not in queue:
>                     new_constraints.append(con)
> 
>             queue = queue[1:] + new_constraints
>     
>         else:
>             queue = queue[1:]

Alright! Now that our affairs are in order, we can start with the algorithm in earnest. What we’ll be doing basically amounts to a depth-first search of the search space. We’ll need an unambiguous ordering of our pieces, so let’s convert our set to a list.
To keep track of our state, we’ll just use a dictionary that our algorithm will be modifying directly.

> pieces = list(pieces)
> z = {}

The search algorithm itself is really straightforward: we’ll fix a variable to a domain value, make sure it doesn’t violate any constraints, and then move on to the next variable. If it does violate a constraint, we move on to the next domain value. If we’re out of domain values, we move back to the previous variable and change that.

> def backtrack(depth):
>     for a in domains[pieces[depth]]:
>         z[pieces[depth]] = a
> 
>         for c in constraints:
>             if (c.p1 == pieces[depth] and c.p2 in pieces[:depth]) or \
>                (c.p2 == pieces[depth] and c.p1 in pieces[:depth]):
>                 if not c.valid(z[c.p1], z[c.p2]):
>                     break
> 
>         else:
>             if depth == len(pieces) - 1:
>                 print "Solution:", z
>             else:
>                 backtrack(depth + 1)

As written, this will just keep looking for solutions until it’s exhausted the search space, but it’s trivial to make it so that it stops after the first result is found, of course.

And that’s that. Now we just invoke everything and let it run.

> ac3()
> backtrack(0)

And we’re done!
As usual, all of the code can be found here, in case you want to try it yourself. If you want an exercise to try at home, find a sensible representation for the eight queens problem and solve that. (Hint: there’s a better one than (row, column).)

Now, is constraint processing a good alternative to the search tree algorithms previously discussed? Obviously not the algorithm I’ve just described; that’s just a naïve DFS without heuristics. It can be improved in a lot of ways: you could sort the list of variables so that the variables with the smallest domains and the most constraints affecting them are first, for example. Or you could go a step further and do dynamic search tree rearrangement using some heuristic, making sure that the variables more likely to cause a constraint violation are filled in first. You could prevent a whole lot of redundant checks using a variety of techniques, like backmarking or backjumping or intelligent backtracking or what have you; there’s a million things you could do.² There’s no shortage of research on constraint processing, and the state of the art is surprisingly advanced.
I’m not terribly fond of constraint processing algorithms, myself, because I get the impression that they’re more complex to implement for no significant gain, but I can see why some people would be.

In the end, the most significant factor is probably what the most natural way to express your problem is. Any problem that can be solved using vanilla search trees can be solved as a constraint problem and vice versa, but most problems are just easier to express one way or the other.

(My AI exam is on Monday, so this will probably be the last post in this series. The only course subject I haven’t covered is version spaces, anyway, and that’s not hugely interesting. Oh, and automated reasoning, but that’s more suited to a book than a blog post.)

---

⁰ Most algorithms only bother with two variables, but it’s entirely possible to formulate this problem as a single constraint on nine variables. Enforcing 9-consistency (see the domain pruning bit later on) would be equivalent to solving it the way we’re doing now, though.

¹ In fact, we’ll only look at a small fraction of that even when we do an exhaustive search, but any advantage is nice to have at this point.

² You could even use a language other than Python and implement it in a way that isn’t dumb!