Backtracking on a 27-node graph coloring problem

Animation by Andrew Moore

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

Back to other constraint satisfaction animations