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.htmlBack to other constraint satisfaction animations