**Go backward to** Solution to part (a)

**Go up to** 7 Solving a CSP via backtracking, arc consistency, hillclimbing

**Go forward to** Solution to part (c)

## Solution to part (b)

The optimal orderings are
[ B, C, E, D, A]
[ B, D, E, C, A]
[ C, B, E, D, A]
[ C, E, B, D, A]
[ D, B, E, C, A]
[ D, E, B, C, A]
[ E, C, B, D, A]
[ E, D, B, C, A]

There each have 49 failing branches.
Some close orderings are:
[ B, C, D, E, A]
[ B, D, C, E, A]
[ C, B, D, E, A]
[ C, E, D, B, A]
[ D, B, C, E, A]
[ D, E, C, B, A]
[ E, C, D, B, A]
[ E, D, C, B, A]

There each have 61 failing branches.
[ B, C, E, A, D]
[ C, B, E, A, D]
[ C, E, B, A, D]
[ E, C, B, A, D]

These each have 64 failing branches.
So how would one go about arguing for a good ordering?
We can look at a strategy that tries to cut out as big a proportion of
the branches as possible at each stage. It doesn't matter what we
choose first. The second choice should make the biggest pruning which
can be done if we choose a node that uses the *>* constraint. This has
cut the possibilities to a few of the pairs. The third constraint then
has to prune as much as possible again. The ones that prune the most
are those that have constraints with both of the first two variables.
The first three variables should either be *{B,C,D}* or
*{C,D,E}*. Note that if a branch gets pruned on the third step, it
doesn't matter what the ordering of the variables is.

Computational
Intelligence online
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999