Depth First Search on a 100-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 100 nodes.

Tries BLUE then RED then BLACK.

Depth first search iterates over all possible colorings
until it finds one with no constraints. It's hopeless
and would take longer than the age of the universe to
solve this problem.

We don't show the whole thing.

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