Click here to download AVI movie

The BACKTRACKING algorithm on a 3-color graph-coloring problem with 100 nodes. Tries BLUE then RED then BLACK. Notice that the third-from-left node on the bottom row actually must be a different color from its two left neighbors in any full solution but it takes a lot of backtracking to find this out. Once it gets the second row complete the rest is easy. It takes 891 steps until it succeeds. See Constraint Satisfaction Lecture notes at http://www.cs.cmu.edu/~awm/tutorials/constraint.htmlBack to other constraint satisfaction animations