Forward Checking on a 27-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 27 nodes.

Tries BLUE then RED then BLACK.

Little dots denote the availability lists
for the nodes.

Notice that unlike backtracking search, Forward
Checking realizes as soon as it tries setting
the node at (row=bottom+1,col=rightmost-1) to
Black that it's not going to be able to
satisfy the top-left node.

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