Click here to download AVI movie

The BACKTRACKING algorithm on a 3-color graph-coloring problem with 27 nodes. Tries BLUE then RED then BLACK. This prunes parts of the depth first search as soon as it notices a violation. But notice how early decisions mean that no matter what it tries, for a long time nothing will work up in the top left node. It takes 65448 steps until it succeeds. See Constraint Satisfaction Lecture notes at http://www.cs.cmu.edu/~awm/tutorials/constraint.htmlBack to other constraint satisfaction animations