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

Tries BLUE then RED then BLACK.

Little dots denote the availability lists
for the nodes.

Once again, it avoids many of the backtracks that
Forward Checking falls victim of.

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

Back to other constraint satisfaction animations