Constraint Propagation with Variable Ordering on a 196-node graph coloring problem

Animation by Andrew Moore

Click here to download AVI movie

The CONSTRAINT PROPAGATION with VARIABLE
ORDERING algorithm on a 3-color 
graph-coloring problem with 196 nodes.

Tries BLUE then RED then BLACK.

Little dots denote the availability lists
for the nodes.

With Variable Ordering (primarily by number
of available values, and secondarily by number
of constraints) it does not take too long
to prove unsatisfiability.

See Constraint Satisfaction Lecture notes at
http://www.cs.cmu.edu/~awm/tutorials/constraint.html