|
|
This is the eighth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography; the fourth was Selected Papers on Analysis of Algorithms; the fifth was Selected Papers on Computer Languages; the sixth was Selected Papers on Discrete Mathematics; the seventh was Selected Papers on Design of Algorithms.) The Fun and Games volume is characterized by the following remarks quoted from its preface.
I've never been able to see any boundary between scientific research and game-playing. ... The topics treated here were often inspired by patterns that are visually compelling, or by paradoxical truths that are logically compelling, or by combinations of numbers and/or symbols that fit together just right. These were papers that I couldn't not write.
I believe that the creation of a great puzzle or a great pattern is a scholarly achievement of great merit, an important contribution to world culture, even though the author of such a breakthrough is often an amateur who has no academic credentials. Therefore I'm proud to follow in the footsteps of the pioneers who have come up with significant new “mind-benders” as civilization developed.
Many years ago I wrote an essay that asked “Are toy problems useful?” [reprinted as Chapter 10 in Selected Papers on Computer Science] in which I discussed at some length my view that students are best served by teachers who present them with well-chosen recreational problems. And I've carried on in the same vein ever since, most recently on pages 7--9 of The Art of Computer Programming, Volume 4A, in a section entitled “Puzzles versus the real world.”
Thus it’s not surprising that many of the chapters in the present book have resulted from my attempts to answer puzzling questions that have no immediately obvious relation to any practical applications of mathematics or of computer science. Or that sometimes I had an urge to embellish or extend the answers to classical enigmas that had previously been resolved. And of course I've also come up with a few new puzzles in the process, several of which I don't yet know how to tackle.
In other words, I believe that diversions are useful, and I've tried in this book to provide useful diversions that meet high standards of quality. Of all the papers that I've written, the ones included here have given me the most personal pleasure---in fact, sheer joy at times! The various chapters include my earliest work as well as my latest. Many of them have an autobiographical flavor, because they're associated with some of the most memorable moments of my life.
Actually I've had great fun with these papers not only when writing them but also when revisiting them, as I was preparing this collection. Now, as I write this preface, I can't help but celebrate the fact that I've finally been able to put together the book that I've always dreamed of writing, a book that best expresses the quirky things that I enjoy. I'm quite sure that this book isn't for everybody; but if you're anything like me, you will enjoy it too, at least in part.
... And then the preface continues by describing the other chapters, which can be summarized more succinctly by quoting from the hype on the back cover:
The present volume, which is the eighth and final book in Knuth’s 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 appealing puzzles, paradoxes, and 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, license plates, and geek art. ... All are found here, together with more than 700 newly created illustrations.
Here’s the table of contents:
(Numbers like P1 and Q99 in this list refer to the corresponding papers in my list of publications. Seventeen of these chapters are published here for the first time; fourteen others appeared in publications of limited circulation and are difficult to find in libraries.)
This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).
Knuth said that this book was his favorite. After reading every word of its 700+ pages I can see why. The book format and the topic allows him to put in whatever he finds interesting. ... One of the best features: Many of the chapters have addenda that were added just recently. This is excellent since an old article needs some commentary about what happened next?. ... The book is a joy to read. I predict that $(\forall p\in P)(\exists C\subseteq CH)[|C|\ge30\land (\forall c\in C)[L(p,c)]]$ where $P$ is the set of people who read this column, $CH$ is the set of chapters of the book, and $L(p,c)$ means that person $p$ liked chapter $c$.
-- William Gasarch, in SIGACT News (June 2014)
Several chapters of the book refer to Internet pages for more detailed information. I've copied the relevant links here so that you can simply click instead of typing a long URL:
Here also is a link to an illustrated writeup by Serhiy Grabarchuk about several puzzles that I've introduced over the years.
As usual, I promise to deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.
Here is a list of all nits that have been picked so far in the first printing (2011); an asterisk (*) marks technical errors that are not merely typographical:
- page 8, line 8 (7 February 2011)
- change "19 November 19" to "19 November"
- page 10, lines 4 and 5 (8 May 2011)
- change "mtn" to "mn" (twice)
- page 25, lines 12 and 13 from the bottom (2 February 2011)
- change "décimale" to "décimales" (twice)
- *page 36, lines 11--14 (7 February 2011)
- insert a blank space before each right single quote mark (four times)
- page 58, line 2 from the bottom (8 May 2011)
- change "Weights of Measures" to "Weights and Measures"
- *page 66, line 7 (6 February 2011)
- change $theta$ to $\theta$
- page 77, lines 12 and 13 (8 May 2011)
- change "that that" to "that"
- page 101, lines 4 and 7 (14 February 2011)
- change "Academie" to "Académie" (twice)
- page 117, line 10 from the bottom (19 December 2014)
- change "John Louis" to "Jon Louis"
- page 120, lines 4 and 5 from the bottom (24 February 2011)
- change "nombres surnaturel" to "nombres surnaturels"
- page 121, replacement for lines 3 and 4 (28 March 2011)
- [An abridgment of this chapter was published in The Mathematical Intelligencer 33,1 (Spring 2011), 33--45.]
- page 123, line 9 (07 April 2012)
- change "Wisconsonites" to "Wisconsinites"
- page 153, in reference [3] (19 September 2022)
- change 'California plates' to 'California license plates'
- page 155, line 13 (18 February 2012)
- change "to appear" to "265--284"
- page 160, insert a new third paragraph to the addendum (14 April 2011)
- Mark Manasse has a wonderful license plate that I learned about too late to include in my original article: His is I DID F9, commemorating the successful factorization of the ninth Fermat number $2^{512}+1$ [see Mathematics of Computation 61 (1993), 319--349; 64 (1995), 1357].
- page 160, also insert a new fourth paragraph (06 July 2011)
- Ron Fagin tells me that, when he was a student at Dartmouth in the mid-1960s, John Kemeny proudly had the New Hampshire license plates LOGIC and SETS.
- page 160, bottom line (04 October 2011)
- change "2010." to "2010; and on 4 October 2011, Eugene Miya saw P♥THON. “What a grin.”
- page 169, line 3 after the illustrations (24 February 2011)
- change "my collection" to "our collection"
- page 170, line 4 after the illustrations (24 February 2011)
- change "my collection" to "our collection"
- page 175, line 5 after the illustrations (24 February 2011)
- change "my collection" to "our collection"
- page 177, line 4 after the illustrations (24 February 2011)
- change "my collection" to "our collection"
- *pages 190 and 191 (12 December 2010)
- the final two chords of this music should change, and several other minor errors should be fixed; see the corrected copy
- page 194, line 2 from the bottom (24 February 2011)
- change "Des arts nouveaux! où Le hasard" to "Du Hasard"
- page 194, bottom line (27 February 2011)
- change "Revue des Revues" to "La Revue des revues"
- page 247, replacement for line 13 (14 August 2012)
- default_msg[TOSS] = default_msg[DROP];
- page 262, line 14 (13 March 2011)
- omit "ditto(ENTER);"
- page 262, line 5 from the bottom (13 March 2011)
- omit "ditto(OUT);"
- page 304, line 11 from the bottom (14 August 2012)
- change 'check,""' to 'check,0'
- page 307, line 4 (09 March 2011)
- change prop[t] to place[t]
- page 313, line 10 (14 August 2012)
- change "hides his treasure" to "leaves his treasure"
- page 317, lines 2 and 11 (21 January 2022)
- change "p++;" to ";"
- page 320, line 6 (09 March 2011)
- change "of that motion" to "of that action"
- page 321 and following (09 March 2011)
- (several functions, such as lookup and is_at_loc, are erroneously listed as type void in the mini-indexes)
- page 324, line 10 from the bottom (14 Aug 2012)
- change "printf" to "if (p) printf"
- page 329, line 12 (14 August 2012)
- change "wish to quit" to "want to quit"
- page 331, replacement for line 1 (14 August 2012)
- report("Peculiar. Nothing unexpected happens.");
- page 344, line -4 (10 August 2012)
- change "change_to(EAT)" to "verb=EAT" (and also remove "change_to" from the mini-index on page 345)
- page 346, line 4 (15 August 2012)
- delete "k=1;"
- page 370, insert new paragraph after line 23 (09 February 2020)
- [Two statements marked ‘bugfix’ have been inserted here, on the recommendation of Arthur O'Dwyer, because they correct a subtle error in Woods’s original implementation.]
- page 371, insert new line of code after line 4 (09 February 2020)
- place[WATER]=limbo; place[OIL]=limbo; /* bugfix */
- page 384, right column, change_to entry (10 August 2012)
- change "122, 129" to "122"
- pages 387, 389, 391, 392 (09 February 2020)
- add "181" to the index entries for limbo, OIL, place, WATER, Woods
- page 391, left column, TOSS entry (14 August 2012)
- change "14, 99" to "14"
- page 400, line -16 (22 August 2011)
- change "Club" to "Club, developed by Murl Deusing,"
- page 400, lines -11 through -9 (22 August 2011)
- change "I've been unable ... Brazier." to "The handsome host who appears in Figure 3 was Art Whitfield."
- page 419, line 6 from the bottom (01 March 2011)
- change "slow to fast, flat" to "flat"
- page 432, line 10 (01 March 2011)
- change "there 179" to "there are 179"
- page 448, line 5 below Table 1 (27 February 2011)
- change "memory" to "memory accesses"
- page 444, line 11 (21 January 2022)
- change "in this way" to "in this heuristic way"
- page 486, line 3 from the bottom (02 March 2011)
- change "obtaining by" to "obtained by"
- page 528, line 13 from the bottom (15 February 2011)
- change "the closed states" to "the 167 closed states"
- page 531, line 14 from the bottom (23 February 2011)
- change "which we already know" to "for which we already know $G(\beta)$"
- page 533, line 9 from the bottom (21 January 2022)
- change "the the self-dual" to "the self-dual"
- page 616, line 6 (13 March 2011)
- change "need for" to "needed for"
- page 684, line 18 (7 February 2011)
- change "Vive" to "Vive la"
- page 703, line 18 (7 February 2011)
- change "Hector" to "Héctor"
- *page 703 (16 January 2011)
- Addendum
I forgot to mention that Edmé Simonot had already implemented Vandermonde’s idea of knotted-string knight’s tours in his Polygraphile of 1872. In fact I encountered two examples of that remarkable puzzle during a visit to the Cleveland Public Library in May 2010, shortly after having designed Figures 33 and 34.- page 705, lines 3 and 4 (4 March 2011)
- change "tributes to be published in ... (March 2011)" to "tributes published in ... (March 2011), 218--220"
- page 715 (15 December 2010)
- insert the picture
after line 3, with credit to William Samuel Parker Robertson
- page 718, left column, new entry (25 February 2011)
- agile methods, 711.
- page 722, left column, new entry (06 July 2011)
- Dartmouth College, 160.
- page 722, left column, Davis entry (28 December 2017)
- change "Chandler" to "Horace Chandler"
- page 724, left column, new entry (25 February 2011)
- extreme methods, 711.
- page 724, new entry (14 April 2011)
- factorization, 160.
- page 724, new entry (06 July 2011)
- Fagin, Ronald, 160.
- page 724, right column, new entry under Fermat (14 April 2011)
- numbers, 160.
- page 724, right column, new entry (19 April 2011)
- Fischer, Alexander, 484.
- page 728, right column, new entry (06 July 2011)
- Kemény, János György (= John George), 160.
- page 730, right column, new entry (14 April 2011)
- Manasse, Mark Steven, 160.
- page 733, right column, new entry (09 February 2020)
- O'Dwyer, Arthus, 370.
- page 735, left column, new entry (04 October 2011)
- Python language, 160.
- page 736, left column, new entry (16 February 2017)
- Robertson, William Samuel Parker, 715.
- page 736, right column, S heuristic entry
- add page 444
- page 737, right column, new entry (25 February 2011)
- silver bullets, 711.
- page 737, right column, new entry (25 February 2011)
- Simonot, Edmé, 703.
- page 740, left column, Vandermonde entry (25 February 2011)
- add page 703
- page 740, right column, new entry (20 September 2011)
- Whitfield, Arthur Raymond “Whit”, 399--400.
- page 741, left column, Woods entry (09 February 2020)
- add page 370
- page 35, line 6 (17 October 2014)
- change "(5)" to "(8)"
- *page 105, line -15 (1 November 2013)
- change $10^{2^{10^{80,000,000,000,000,003}}}$ to $10^{2^{10^{80,000,000,000,000,000}+3}}$
- page 107, line 4 (27 March 2014)
- change "subjection" to "subject"
- *page 198, line 5 after Variation 3 (14 January 2014)
- change "melody note." to "melody note and force the desired chord."
- *page 244, line 14 (09 October 2014)
- change "PILLOW);" to PILLOW); new_word("velve",PILLOW);"
- *page 332, lines 6--9 (3 September 2012)
- move line 6 ("if (toting... crash*/") to line 9 between "smash:" and "prop"
- *page 382, line -8 (6 October 2018)
- change $\le k$ to $<k$
- *page 382, line -4 (6 October 2018)
- change $[j]-k$ to $[j]+1-k$
- *page 382, line -4 (29 April 2019)
- change $\equiv k+1$ to $\equiv k$
- *page 399, lines 3 and 4 (31 December 2014)
- change "included three ... abigail, ablating, abuser." to "included two ... abigail and ablating."
- *page 399, line 10 (31 December 2014)
- change "87+9+1+1=98" to "87+8+1+1=97"
- page 458, line 12 (07 January 2019)
- change "R, S, U" to "R, T, U"
- *page 568, new paragraph to begin the Addendum (23 August 2021)
- I learned later that Theorem 1 had already been proved by F. Rhodes and S. Wilson, “Connectivity of knight’s graphs,” Proceedings of the London Mathematical Society (3) 67 (1993), 225–242. Furthermore, Theorem 5 had been proved and generalized to larger boards by I. J. Dejter, “(1,2k)-chessknight Hamiltonian cycles invariant under quarter turns,” Scientia Series A: Mathematical Sciences 2 (1988), 39–51.
- *page 570, replacement for the final paragraph about tsplib (23 August 2021)
- The biggest news, however, is a breakthrough result that I thought I'd never live to see: Nikolai Beluhov, “A proof of Willcocks’s conjecture,” arXiv:1708.05810 [math.CO], 25 pages.
- *page 583, line 8 from the bottom (24 July 2015)
- change "twice" to "four times"
- page 611, bottom two lines (13 May 2014)
- change "tiles” (2010) [to appear]." to "tiles,” Theoretical Computer Science 414 (2012), 20--37."
- page 719, left column, new entry (23 August 2021)
- Beluhov, Nikolai Ivanov, 570.
- page 722, right column, new entry (23 August 2021)
- Dejter, Italo José, 568.
- page 736, left column, new entry (23 August 2021)
- Rhodes, Frank, 568.
- page 741, left column, new entry (23 August 2021)
- Wilson, Stephen Edwin, 568.
- page 734, left column, Padberg entry (29 October 20)
- change 'William' to 'Wilhelm'
- page 742, last line (22 December 2019)
- [this character has now grown a little tuft of hair at the right]
I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 1B, Stanford University, Stanford, CA 94305-9015 USA. In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.
I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.
DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.
Don Knuth’s home page
Don Knuth’s other books