Constraint Propagation on a 27-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 27 nodes.

Tries BLUE then RED then BLACK.

Little dots denote the availability lists
for the nodes.

Notice that unlike forward checking search, Constraint
Propagation realizes very early on (on its third step)
that (row=bottom+1,col=rightmost-1) must not be black
and so (row=bottom,col=4) must not be red. It does
better than forward checking and MUCH better than
backtracking!

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