Backtracking on a 9-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 9 nodes.

Tries BLUE then RED then BLACK.

This prunes parts of the depth first search
as soon as it notices a violation. Beats the
heck out of DFS, though it still backtracks
a little bit. 

It takes 15 steps until it succeeds. 

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