Constraint Propagation on a 196-node graph coloring problem

Animation by Andrew Moore

Click here to download AVI movie

The CONSTRAINT PROPAGATION 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.

This problem has no three color solution. But it
takes CP impractically long (probably years) to
realize it.

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