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.htmlBack to other constraint satisfaction animations