Backtracking on a 27-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 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.html