Backtracking on a 100-node graph coloring problem

Animation by Andrew Moore

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.html