Backtracking on a 9-node graph coloring problem

Animation by Andrew Moore

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

Back to other constraint satisfaction animations