Forward Checking on a 49-node graph coloring problem

Animation by Andrew Moore

Click here to download AVI movie

The FORWARD CHECKING algorithm on a 3-color 
graph-coloring problem with 49 nodes.

Tries BLUE then RED then BLACK.

Little dots denote the availability lists
for the nodes.

Notice that although it only takes 180 steps
it frequently has to do quite a bit of backtracking.

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