% CHANGES TO FASCICLE V4F7 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2025 by Donald E. Knuth % This file may be freely copied provided that no modifications are made. % All other rights are reserved. % % Three levels of changes to the books are distinguished here: % % "\bugonpage" introduces the correction of an error; % "\amendpage" introduces new material for future editions; % "\improvepage" introduces ameliorations of lesser importance. % % (Changes introduced by \improvepage do not appear in the hardcopy listing.) % % Also, "\planforpage" introduces some of the author's half-baked intentions. % % NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE % tex "\let\indexeject+ \input err4f5" \newif\ifall % \alltrue means show the trivial items too \relax % hook \def\vertical{|} \def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname} \catcode`|=\active \let|\inref \input \jobname.ref \catcode`|=12 \input taocpmac % use the format for TAOCP, with modifications below \def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change \def\bugonpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\bugoverall#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Important Changes Throughout!}\enspace \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\amendpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\improvepage#1.#2 #3 (#4) {\ifall \medbreak\ninepoint \line{\kern-6pt{\sl Page #2\enspace #3\/} \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\noindent} \def\planforpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.} \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent} \let\endchange=\fi \def\nl{\par\noindent} \def\nlh{\par\noindent\hangit} \def\hangit{\hangindent2em} \def\cutpar{{\parfillskip=0pt\par}} \def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy" #3 \ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi \ \ifnum #1<97 \hundred#1\else19#1\fi} \def\hundred{20} % the "century" for dates before '97 \def\ex #1. [#2]{\ninepoint \textindent{\bf#1.}[{\it#2\/}]\kern6pt} \def\EX #1. [#2]{\ninepoint \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt} \def\foottext#1{\medskip \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint \smallskip\textindent{#1}} \def\volheadline#1{\line{\hss\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill\hss}} \def\refin#1 {\let|\inref \input #1.ref \let|\crossref} \let\defaultpointsize=\tenpoint %%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{INTRODUCTION} \let\rhead=\lhead \titlepage \volheadline{THE ART OF COMPUTER PROGRAMMING} \bigskip \volheadline{ERRATA TO VOLUME 4 FASCICLE 7} \bigskip \noindent This document is a transcript of the notes that I have been making in my personal copy of {\sl The Art of Computer Programming}, Volume~4, Fascicle~7, since it was first printed in 2025. \ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,'' and ``improvements''\dash---appear, indicated by four \else Three levels of updates\dash---``errors,'' ``amendments,'' and ``plans''\dash---appear, indicated by three \fi different typographic conventions: \begingroup\def\hundred{17} \bugonpage 0.666 line 1 (76.07.04) Technical or typographical errors (aka bugs) are the most critical items, so they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page number. The date on which I first was told about the bug is shown; this is the effective date on which I paid the finder's fee. The necessary corrections are indicated in a straightforward way. If,~for example, the book says `$n$' where it should have said `$n+1$', the change is shown thus: \smallskip $n$ \becomes $n+1$ \endchange \amendpage 0.666 line 2 (89.07.14) Amendments to the text appear in the same format as bugs, but without the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known about or thought of when I wrote the original text, so I added them later. The date is the date I drafted the new text. \endchange \def\hundred{19} \planforpage 0.666 line 3 (17.11.20) Plans for the future represent a third kind of item. In such notes I~sketched my intentions about things that I wasn't ready to flesh out further when I~wrote them down. You can identify these items because they're written in slanted type, and preceded by a bunch of dots `\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on which I recorded the plan in my files. \endchange \improvepage 0.666 line 4 (38.01.10) The fourth and final category\dash---indicated by page and line number in smaller, slanted type\dash---consists of minor corrections or improvements that most readers don't want to know about, because they are so trivial. You wouldn't even be seeing these items if you hadn't specifically chosen to print the complete errata list in all its gory details. Are you sure you wanted to do that? \endchange \endgroup \ifall\else\medskip\ninepoint My personal file of updates also includes a fourth category of items, not shown in this list. They are miscellaneous minor corrections or improvements that most readers don't want to know about, because they are so trivial. If you really want to see all of the gory details, you can download the full list from Internet webpage $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$ by selecting the ``long form'' of the errata. \fi \medskip \tenpoint \beginconstruction The ultimate, glorious, future editions of Volumes 1--5 are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4 these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, January 2025} \bigskip \bigskip {\quoteformat In spite of my respect for you, I am not convinced by all of your changes. \author ERNEST ANSERMET, letter to Igor Stravinsky (28 November 1929) % Stravinsky in Pictures and Documents, by Stravinsky and Craft (1978) p529 \bigskip For the first time in many years, I've pulled out a copy and read a few chapters to see how much my voice may have changed over time. I confess to wincing every so often at a poorly chosen word, a mangled sentence, .\thinspace.\thinspace. I cannot honestly say, however, that the voice in this book is not mine. \author BARACK OBAMA, {\sl Dreams From My Father\/} (2004) % preface to the 2004 edition, page ix \vfill\eject } \def\today{\number\day\space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} %%%%%%%%%%%%%%% CHANGES FOR VOLUME 4 FASCICLE 7 %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO V4F7: CONSTRAINT SATISFACTION} \def\rhead{CHANGES TO V4F7: CONSTRAINT SATISFACTION} \titlepage \volheadline{CONSTRAINT SATISFACTION} % the fascicle title \bigskip \rightline{Copyright \copyright\ 2025 Addison\with Wesley} \rightline{Last updated \today} \bigskip %\rightline{\sl Most of these corrections have already been made in % recent printings.} %\medskip %\noindent Important note: The changes below include nearly every difference %between the paperback fascicle and the first printing of Volume 4C, %first published in Umbruary 202x. % All subsequent changes can be found in the errata list for that volume. \smallskip \let\defaultpointsize=\tenpoint \improvepage 4f7.10 line $-15$ (25.04.28) between adjacent faces \becomes between the adjacent faces \endchange \improvepage 4f7.79 line 4 (25.01.01) no-three-in-a-line \becomes no three in a line \endchange \bugonpage 4f7.114 line 4 of exercise 22 (25.01.18) \ninepoint $(15,20,10,12,6)$ \becomes $(12,20,15,10,6)$ \endchange \amendpage 4f7.115 new rating for exercise 28 (25.09.11) \ninepoint [{\it M27\/}] \becomes [{\it M37\/}] \endchange \amendpage 4f7.115 new rating for exercise 29 (25.09.11) \ninepoint [{\it 24\/}] \becomes [{\it 34\/}] \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \bugonpage 4f7.162 replacement for last seven lines of answer 27 (25.09.11) \noindent edge in common. A~milder violation occurs when $a>b=c>d,ドル because six faces meet at vertex $(1,1,b)$. Four faces meet at that vertex when $a>b=d>c$.\par But the other cases are fine: {\it Case 1}, $a=b=c\ge d$. {\it Case 2}, $a=b>\max\{c,d\}$. {\it Case 3}, $a>b=c=d$. {\it Case 4}, $a>b>\max\{c,d\}$. \def\TVP/{{\mc 3VP}}% When we take symmetry into account, these cases contribute respectively $\bigl({10\choose1}+4{10\choose2},4{10\choose2}+8{10\choose3},4{10\choose2}, 8{10\choose3}+16{10\choose4}\bigr)$ valid \TVP/s, a total of 5830.\par (And the $B^4$ histoscapes of 2ドル\times2$ matrices with $a_{ij}2m$ or $j>2n$ or $k>2t-2$.)\par Third, mark all the ``visible'' edges, by doing the analogous three operations for all $(i,j,k)$ with $\ibar+\jbar+\kbar=2$ and $b_{ijk}=1$: If $\ibar=1$ and $b_{(i\pm2)jk}=0,ドル set $b_{(i\pm1)jk}\gets1$; if $\jbar=1$ and $b_{i(j\pm2)k}=0,ドル set $b_{i(j\pm1)k}\gets1$; if $\bar k=1$ and $b_{ij(k\pm2)}=0,ドル set $b_{ij(k\pm1)}\gets1$.\par Fourth, mark all the vertices, by doing those same three operations for all $(i,j,k)$ with $\ibar+\jbar+\kbar=1$.\par \endchange \improvepage 4f7.164 last line of answer 30 (25.09.12) square torus \becomes square doughnut \endchange \bugonpage 4f7.164 line 5 of answer 31 (25.06.07) True \becomes False \endchange \bugonpage 4f7.171 in answer 59 (25.09.15) line 2: only 90\% squashed: $\vcenter{\def\epsfsize#1#2{.2#1}\epsfbox{\figdir/3d-to-2d.38}}$. \becomes % Guenter Rote didn't like that one ... see his letter of 2025年05月24日! only 80\% squashed: $\vcenter{\epsfbox{\figdir/v4c.4059}},円$.\nl lines 5 and 6: It does not \dots~David''\dash---so HC \becomes\nl He aligned the cubes in a more symmetrical way, so that the blank region in the middle forms a ``^{star of David}''; thus the HC \endchange \bugonpage 4f7.174 last line of answer 68 (25.06.07) 1ドル\adj(m-1)$ \becomes 0ドル\adj(m-1)$ \endchange \amendpage 4f7.202 new line to follow the caption of Fig.~A--14 (25.03.25) \noindent N.~Beluhov generalizes (v) to leapers in \arXiv:2503.18700 [math.CO] (2025), 12~pages.\tighten \endchange \bugonpage 4f7.235 in step F3 (25.03.26) $s$ \becomes $s'$\qquad(five changes) \endchange \bugonpage 4f7.236 in answer 353 (25.03.26) $s$ \becomes $s'$\qquad(three changes) \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 4f7.264 and following (25.01.01) Miscellaneous changes to the existing index of Volume~4 Fascicle~7 are collected here, including corrections and amendments to the old entries as well as new entries that are occasioned by the new material. Thus, the lines of the full index that have changed serve also as an index to the present document. However, when a correction or amendment has caused an old index entry to be deleted, the deletion is usually not indicated. \input exotic \begindoublecolumns \begingroup \indexformat \gdef\Uni1.08:{\bitmap24:1.08:} \hangindent2em Beluhov, Nikolai Ivanov ({\rus Belukhov, Nikolai0 Ivanov}), 186, 202--204, 221, 222. % 2nd Gallery of fillomino puzzles, 220. % 2nd Gallery of knight's grids, 202--203. % 2nd General position, 11, 117, 172. % 2nd IJCAI: {\it International Joint Conference on Artificial Intelligence\/} (1969--). % 2nd; there was no good reason for indexing page 225 Leaper, 202, 204, 261. % 2nd No-three-in-line, 79, 146. % 2nd Square doughnut, 164. % 2nd \vfill % TEMPORARY \enddoublecolumns \endgroup \endchange \bye [The next printing will be the 2nd.] not listed above: page 33, 5 lines before (56), Hmm -> Hmmm page 44, line -8, not as much space between lines page 166, line 5 of answer 38, "(Berlin, 1773)" page 181, line -3 of answer 100, [see...] -> (see...) page 201, better wording on bottom line page 226, line -3, Hmm -> Hmmm page 251, line 7, New Jersey, 1941 page 258, last line of answer 472 has a spurious space ARTICLES "TO APPEAR" THAT ARE STILL PENDING: van Dongen's proof (see answer 278)

AltStyle によって変換されたページ (->オリジナル) /