Don Knuth: Computer Musings: Fun With Binary Decision Diagrams (BDDs) June 5, 2008

Don Knuth says: "I'll discuss some of the adventures I've had during the past year while reading hundreds of papers and writing dozens of programs that relate to the fascinating family of data structures called BDDs. With these tools I've been able to answer questions that I never before thought I'd able to resolve in a reasonable amount of time. For example: There are exactly 301,312,268,736 ways to color a map of the 48 continental United States using four colors, with 12 states of each color (and of course with no adjoining states the same color). BDDs make it possible to determine this number in a few seconds, after making only about 150 million accesses to computer memory. Then we can readily find uniformly random map colorings, optimum colorings, and solve other related problems without explicitly listing all the possibilities. "

Official Website: http://sunburn.stanford.edu/~knuth/musings.html