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

Back to other constraint satisfaction animations