Selected Papers on Fun and Games

Donald Knuth's influence in computer science ranges from the invention of methods for translating and defining programming languages to the creation of the TEX and METAFONT systems for desktop publishing. His award-winning textbooks have become classics that are often given credit for shaping the field; his scientific papers are widely referenced and stand as milestones of development over a wide variety of topics. The present volume, which is the eighth and final book in his series of collected papers, is the one that he has saved up for dessert: It's a potpourri devoted to recreational aspects of mathematics and computer science, filled with the works that gave him most pleasure during his 50-year career. Here you'll find puzzles, paradoxes, and appealing patterns: visual, numerical, and musical.

Nearly fifty of Knuth's works are collected in this book, beginning with his famous first paper in MAD Magazine, and containing several similarly delightful spoofs written "in a jugular vein." Knuth's well-known introduction to the "dancing links" algorithm for combinatorial searches is accompanied by several chapters that shed new light on the age-old problem of knight's tours on a chessboard. There are chapters about word games, computer games, and even basketball, together with topics of modern folk culture such as traffic signs and license plates. Seventeen of these chapters are being published for the first time; fourteen others have appeared only in publications of limited circulation that are difficult to find in libraries. All are found here, together with more than 700 newly created illustrations. CSLI Lecture Notes number 192

Donald E. Knuth is the Fletcher Jones Professor of Computer Science emeritus at Stanford University.

Contents

January 2011