Depth First Search on a 9-node graph coloring problem

Animation by Andrew Moore

Click here to download AVI movie

The DEPTH FIRST SEARCH algorithm on a 3-color 
graph-coloring problem with 9 nodes.

Tries BLUE then RED then BLACK.

Depth first search iterates over all possible colorings
until it finds one with no constraints. It's frustrating
to watch it fill in the values the first time and go
to full depth of 9 in the search tree without checking
for constraint violations along the way!

It takes 6109 steps until it succeeds. 
We don't show the whole thing.

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