% CHANGES TO VOLUME 4B OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2022, 2023, 2024 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 err4b" \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\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{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}} \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 4B} \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~4B since it was first printed in 2022. \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 {\sl The Art of Computer Programming\/} 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 1B, Stanford University, Stanford CA~94305-9015, 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~4C these days, I~will try to reply to all such messages within a year of receipt. Current news is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, July 2022} \bigskip \bigskip {\quoteformat Next to the promulgation of new truth, the best thing, I conceive, that a man can do, is the recantation of published error. \author JOSEPH LISTER (1878) % Trans. Pathol. Soc. Lond. 29 (1878), 425--467; % I saw it in Notes&Records 67(2013)228 in note 23 by R Richardson \bigskip\bigskip \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 4B %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 4B: COMBINATORIAL ALGORITHMS, PART 2} \let\rhead=\lhead \titlepage \volheadline{COMBINATORIAL ALGORITHMS, PART 2} \bigskip \rightline{Copyright \copyright\ 2022, 2023, 2024 Addison\with Wesley} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \def\bland{@\land@} % \land as wide as \xor \def\blor{@\lor@} \def\nbool#1{\mathbin{\mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}} \def\nimp{\?\nbool\supset\?} \bugonpage 4b.ix lines 10 and 11 (23.01.06) Mar-ijn \becomes Ma-rijn \endchange \improvepage 4b.x line $-3$ (23.11.24) For example, $\nu@10=2$, $\lambda@10=3$, $\rho@10=1$. \becomes\nl For example, $\nu@18=2$, $\lambda@18=4$, $\rho@18=1$. \endchange \improvepage 4b.xiv running head (23.04.09) [delete this page number and running head; put `xiv' at bottom, centered] \endchange \amendpage 4b.xv replacement for lines 11--13 (22.11.26) \ninepoint\smallskip \def\0 #1 |#2|{\line{{#1}\leaders\hbox to 1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#2}}}% \def\1 #1 #2 |#3|{\line{\hbox to 2.25em{#1\hfil}{#2}\leaders\hbox to 1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#3}}}% \def\2 #1 #2 |#3|{\line{\hskip2.25em \hbox to 2.95em{#1\hfil}{#2}\leaders \hbox to 1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#3}}}% \0 {\tenssbx Chapter 7\dash---Combinatorial Searching} |[4A.1\rlap]| \smallskip \1 7.2. Generating All Possibilities |[4A.281\rlap]| \2 7.2.1. Generating Basic Combinatorial Patterns |[4A.281\rlap]| \endchange \amendpage 4b.2 in {\eq(9)} (22.12.25) $(\E XY)$ \becomes $\E(XY)$ \endchange \amendpage 4b.27 lines 3 and 4 of exercise 135 (22.12.05) \ninepoint either ($p_kl$ and $q_l>k$ and $q_{l+1}l$ and $p_l>k$ and $p_{l+1}k$ and $p_{l+1}l$) or ($q_{k+1}k$ and $q_k>l$). \endchange \improvepage 4b.33 in step W4 (22.11.27) [Append `(Otherwise stop.)', to match steps B5 and B5*.] \endchange \bugonpage 4b.37 line 17 (23.02.15) to run though \becomes to run through \endchange \bugonpage 4b.42 in the caption to Table 1 (22.11.27) \ninepoint \.{0000} \becomes \.{000}\nl \.{150f} \becomes \.{15f}\nl \.{MEM[40d]} \becomes \.{MEM[4d]} \endchange \bugonpage 4b.43 line 2 after Table 2 (22.11.27) \.{200} through \.{204} \becomes \.{20} through \.{24} \endchange \amendpage 4b.49 first line of step E5 (24.01.28) If $d=0$, terminate. Otherwise set $D\gets D\cdot d$ and $X_{@l}\gets y_I$, \becomes\nl Set $D\gets D\cdot d$, and terminate if $d=0$. Otherwise set $X_{@l}\gets y_I$, \endchange \amendpage 4b.49 replacement for the final six lines (24.01.28) \noindent know roughly how many there are; Algorithm E will tell us the approximate number. Indeed, the expected final value of~$D$ is exactly the total number of solutions, because every solution $X_1\ldots X_{@l}$ constructed by the algorithm is obtained with probability $1/D$, in a case where $D>0$. Note that there may be another criterion for successful termination in step~E2, even though $l$~might still be $\le n$. \endchange \bugonpage 4b.50 line $-2$ (23.11.11) they defend \becomes they defined \endchange \amendpage 4b.55 new rating for exercise 15 (23.06.14) \ninepoint [{\it\HM42\/}] \becomes [{\it\HM44\/}] \endchange \bugonpage 4b.58 exercises 41 and 42 (22.11.27) \ninepoint \.{MEM[40d]} \becomes \.{MEM[4d]}\nl \.{MEM[904]} \becomes \.{MEM[94]}\nl \.{MEM[a0d]} \becomes \.{MEM[ad]} \endchange \improvepage a4b.68 line 2 after Table 1 (22.12.16) to cover a given item~$i$: \becomes to cover the item whose number is~$i$: \endchange \improvepage 4b.90 near the top (22.09.30) line 2: like cover$(i)$ \becomes like cover$(i)$ in \eq(12)\nl line 3: like hide$(p)$ \becomes like hide$(p)$ in \eq(13) \endchange \bugonpage 4b.91 line $-6$ (22.12.17) only 5.2 G$\mu$ \becomes only 4.5 G$\mu$ \endchange \bugonpage 4b.102 in {\eq(86)} (23.01.19) $60741+$ \becomes $60742-$ \endchange \amendpage 4b.102 four lines after {\eq(86)} (23.08.03) average length $n$ \becomes average length $n/2$ \endchange \bugonpage 4b.110 line 1 of step P5 (23.01.02) of its option, go \becomes of its option, or if $\.{COLOR($x$)}\ne0$, go \endchange \bugonpage 4b.111 line 11 (22.12.14) 30,286,432 solutions \becomes 30,258,432 solutions \endchange \improvepage 4b.112 the line before {\eq(108)} (23.07.03) remarkable pairing \becomes remarkable Langford pairing \endchange \improvepage 4b.135 lines 8 and 9 of exercise 103 (23.01.03) \ninepoint twelve-tone row \becomes {\it twelve-tone row} \endchange \amendpage 4b.136 append a sentence to exercise 111 (23.03.30) \ninepoint (Crossword puzzle diagrams are black-and-white grids such as those in exercise 1.3.2--23.) \endchange \bugonpage 4b.138 line 8 of exercise 121 (23.01.07) \ninepoint (2, 3, 3, 57) \becomes (2, 2, 3, 57) \endchange \improvepage 4b.142 line 7 (23.02.13) \ninepoint the boundary of \becomes the boundary path of \endchange \improvepage 4b.145 line 3 of exercise 162 (23.11.04) eight of the possible \becomes eight of the ten possible \endchange \amendpage 4b.145 new rating for exercise 171 (23.11.14) \ninepoint [{\it 25\/}] \becomes [{\it 35\/}] \endchange \amendpage 4b.145 and 146 in exercise 172 (23.01.03) \ninepoint [change `snake-in-the-box' to simply `snake', in five places] \endchange \amendpage 4b.146 new rating for exercise 175 (24.03.27) \ninepoint [{\it 21\/}] \becomes [{\it 22\/}] \endchange \bugonpage 4b.146 lines 2 and 4 of exercise 175 (24.03.27) \ninepoint $a_i$ \becomes $r_i$ \endchange \amendpage 4b.159 new rating for exercise 300 (23.10.27) \ninepoint [{\it 23\/}] \becomes [{\it 24\/}] \endchange \amendpage 4b.160 new rating for exercise 305 (23.02.03) \ninepoint [{\it 25\/}] \becomes [{\it 28\/}] \endchange \amendpage 4b.161 new rating for exercise 306 (23.02.04) \ninepoint [{\it 30\/}] \becomes [{\it 32\/}] \endchange \amendpage 4b.161 in exercise 306 (23.01.03) \ninepoint [change `snake-in-the-box' to simply `snake', in two places] \endchange \amendpage 4b.172 new first paragraph for exercise 372{(b)} (22.12.06) \begingroup\advance\parindent by 4pt\advance\thickmuskip-1mu \ninepoint\item{b)} A {\it twintree\/} is a data structure whose nodes~$x$ have four pointer fields, \.{L0($x$)}, \.{R0($x$)}, \.{L1($x$)}, \.{R1($x$)}. It defines two binary trees $T_0$ and $T_1$ on the nodes, where $T_\theta$ is rooted at \.{ROOT$\theta$} and has child links $(\.{L$\theta$},\.{R$\theta$})$. These two trees satisfy inorder$(T_0)={\rm inorder}(T_1)= x_1\ldots x_n$; $\.{L0($x_k$)}=\Lambda$ $\iff$ $\.{L1($x_k$)}\ne\Lambda$, for $10$ and $k=j+1$, or $i'>0$ and $l=j'+1$, in order to force `\.{123456789}' on the top row.\par With that top row and with $\alpha={}$transposition, Algorithm C produces 30,258,432 solutions in 171~gigamems. (These solutions were first enumerated in 2005 by E.~Russell; see {\tt www.afjarvis.org.uk/sudoku/sudgroup.html}.) \endchange \amendpage 4b.444 line 1 of answer 115 (23.01.02) $b'_{yk}$ and $B'_{y'l}$ \becomes $b'_{yk}$ \endchange \bugonpage 4b.446 new solution for answer {121(c)} (23.01.08) \indent(c) With $\delta RU$ in the middle, another solution has $C_{k-1}$, $D_{k-1}$, $A_{k-1}$, $B_{k-1}$ at the corners. With $\delta LD$, another solution has corners $B_{k-1}$, $A_{k-1}$, $D_{k-1}$, $C_{k-1}$. Both of those solutions work with $\delta LU$ and $\delta SU\?$; and $\delta SU$ also has 54 additional solutions, with $C_{k-2}$ in the upper left corner. They use $\delta\{\{L,P,S,T\}\{J,U\},RU\}$ in the middle of row $2^{k-2}$, and independently $\delta\{L,K,P,R,S,T\}U$ in the middle of row $3\cdot2^{k-2}$. \endchange \bugonpage 4b.450 lines 4 and 5 of answer 133 (23.01.16) We save a factor \dots\ another factor \becomes Remove options with non-\.a on the border; also limit \.{aaaa} to four border positions; and save another factor \endchange \bugonpage 4b.455 line 11 (22.12.20) $q\equiv x$ (modulo~2) \becomes $q\equiv x/q$ (modulo~2) \endchange \amendpage 4b.457 line 22 (23.06.19) 8-cube \becomes eight-cube \endchange \amendpage 4b.459 line 13 of answer 151 (22.11.05) with Algorithm X \becomes with Algorithm X and exercise 413 \endchange \bugonpage 4b.462 line 3 of answer 162 (23.10.13) $r_{j+1}$ $c_{k+3}$ $a_{j+k+3}$ $b_{j-k-3}$ \becomes $r_{j+1}$ $c_{k+3}$ $a_{j+k+4}$ $b_{j-k-2}$ \endchange \bugonpage 4b.462 in answer 162 (23.10.13) line 5: multiplicity. \becomes multiplcity, and we'll use the sharp preference heuristic.\nl line 8: 1.2 teramems. \becomes 150 megamems.\nl line 10: Only 35 G$\mu$ \becomes Less than 200 M$\mu$\nl line 13: 6 teramems \becomes 180 megamems\nl and in the largest displayed solution, put shading on the $\cal Q_5$. \endchange \bugonpage 4b.463 replacement for answer 171 (23.11.14) \ans171. Let there be ten primary items $v$, for $0\le v<10$; also fifteen primary items $\#uv$, for each edge $u\adj v$, where the edges are $0\adj1\adj2\adj3\adj4\adj0$, $0\adj5$, $1\adj6$, $2\adj7$, $3\adj8$, $4\adj9$, and $5\adj7\adj9\adj6\adj8\adj5$. Let there be $26\cdot10$ secondary items $\.a_v$ through~$\.z_v$, for $0\le v<10$; also $26\cdot30$ secondary items $\.a_{uv}$ through~$\.z_{uv}$, for $u\nadj v$; also a secondary item~$w$ for each word in, say, \.{WORDS}(1000). There are 26 options, `$\#uv$ $\.a_u{:}1$ $\.a_v{:}1$' through `$\#uv$ $\.z_u{:}1$ $\.z_v{:}1$', for each edge. And there are 10 options for each word; for example, the options for \.{added} at vertex~0 are `0 $\.a_v{:}1$ $\.b_v{:}0$ $\.c_v{:}0$ $\.d_v{:}1$ $\.e_v{:}1$ $\.f_v{:}0$ \dots\ $\.z_v{:}0$ $\.a_{02}$ $\.a_{03}$ $\.a_{06}$ $\.a_{07}$ $\.a_{08}$ $\.a_{09}$ $\.d_{02}$ \dots\ $\.e_{09}$ \.{added}'.\tighten\par Every solution will be obtained at least 120 times, because the Petersen graph has 120 automorphisms, and the \#$uv$ options might apply more than once. But symmetry can be broken by introducing additional secondary items for pairwise ordering, or by modifying Algorithm C to choose the labels of 0, 1, and 3 first (see exercise 122).\tighten\par There are two solutions in \.{WORDS}(834), namely \.{muddy}, \.{thumb}, \.{books}, \.{knock}, \.{ended}, \.{apply}, \.{fifth}, \.{grass}, \.{civil}, (\.{refer} or \.{fewer}). \endchange \amendpage 4b.464 lines 5 and 6 of answer 172 (23.02.02) ${}=2$. For the path \dots\ $=1$ \becomes ${}=2$. We can safely omit options where $v_i\adj v_j$ and $a_i=a_j=1$; they force a triangle. For the path problem, the starting vertex should have $d$ options, with $a_1+\cdots+a_d=1$ \endchange \amendpage 4b.464 line 4 of answer 172{(a)} (23.01.03) snake-in-the-box \becomes snake \endchange \amendpage 4b.464 in answer 172{(a)} (23.02.02) line 5: 6 T$\mu$ \becomes 270 G$\mu$\nl line 12: 13 M$\mu$ \becomes 54 M$\mu$\nl line 16: (Algorithm M \dots\ 625 G$\mu$ \becomes (If we force the first step downward, Algorithm~M finds the $7!^2=25401600$ solutions in 365~G$\mu$\nl line 21: in 17~G$\mu$, despite having 16788 options of total length 454380(!). \becomes in 9.4~G$\mu$, despite having 10422 options of total length 281934(!). \endchange \bugonpage 4b.464 replacement for most of the last paragraph (23.02.02) \indent Now let's \dots\ dual transposition. \becomes\nl\indent Now let's consider paths that start in cell $(0,1)$ and do not end in a corner. (i)~No such solutions have 32 kings (proved in 166 G$\mu$). (ii)~Knights, however, yield a big surprise: There's a unique path of length~33, doubly counted! (Found in 43~G$\mu$.) (iii)~Bishop paths can't have length~12 unless they start or end in a corner. (iv)~There are $N=(n-1)!^2-2(n-2)!^2$ solutions where the rook first moves down, and $N$ where it first moves sideways. Of these, $2(n-2)!^2$ end at $(1,n-1)$ and are equivalent to those ending at $(n-2,0)$; $(n-2)!^2$ end at $(n-1,n-2)$ and are double-counted by central symmetry; $(n-2)!^2-(n-2)!$ end at $(1,0)$ and are double-counted by transposition; $(n-2)!^2-(n-2)!$ end at $(n-2,n-1)$ and are double-counted by dual transposition. \endchange \bugonpage 4b.465 line 1 (23.02.02) So there are \dots\ 47691936 \becomes So there are $2(n-1)!^2-9(n-2)!^2+2(n-2)!=46139040$ \endchange \amendpage 4b.465 line 6 (23.02.02) fast, except that the kings need 6.3 T$\mu$. \becomes fast; kings need the max time (170~G$\mu$). \endchange \bugonpage 4b.465 line 5 of answer 172{(b)} (23.3.16) bishop has 36 \becomes bishop has 72 \endchange \bugonpage 4b.465 lines 7 and 8 of answer 172{(b)} (23.01.03) under both horizontal and vertical reflection. Every rook snake-in-the-box \becomes under reflection about either diagonal. Every rook snake \endchange \amendpage 4b.465 and 466, replacement for final paragraphs of answer 172 (23.09.08) Nikolai \dots\ [To appear.] \becomes\nl \indent The maximum length of an $n\times n$ snake king path when $n=100$ was the topic of a math olympiad problem in 2008, posed by A. and M.~Chapovalov. Nikolai Beluhov has shown that such maximum paths can be characterized completely; they're related to spirals when $n$ is even, and to stamp-folding when $n$ is odd(!). When $n\ge6$ is even, exactly $2n+(n\mod4)/2$ such paths are distinct under symmetry, and they all start in a corner. Furthermore there are exactly six distinct snake king {\it cycles\/} of length $n^2\!/2-1$, when $n\ge8$ is a multiple of~4. Beluhov has also proved that the longest snake paths and cycles of a {\it knight}, on an $m\times n$ board, have length $mn/2-O(m+n)$. [See {\sl Enumerative Combinatorics and Applications\/ \bf3:2} (2023), \#S2R16, 1--23.] \endchange \amendpage 4b.466 replacement for Fig.\ A--3 and the three previous lines (23.10.12) \indent (b,\thinspace c,\thinspace d) See Fig.\ \fig A--3/. The knight puzzles with labels $\ge6$, and the bishop puzzles with labels 0, 10, and 12, are due to N.~Beluhov; the others are mostly due to F.~Stappers (and are minimum if they have $<5$ clues). Solutions can be found in Appendix~E.\par $$\def\epsfsize#1#2{.3#1} \def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}} \centerline{\\51\enspace\\52\enspace\\53\enspace\\54\enspace\\55\quad\\57}$$ $$\def\epsfsize#1#2{.32#1} \def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}} \centerline{\\31\enspace\\32\enspace\\33\enspace\\34\enspace\\35}$$ $$\def\epsfsize#1#2{.32#1} \def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}} \centerline{\\36\enspace\\37\enspace\\38\enspace\\39\enspace\\59}$$ \endchange \amendpage 4b.467 in answer 175 (24.03.27) line 5: $a_i=a+1$ \becomes $r_i=r+1$\nl line 5: $2a+1$ \becomes $2r+1$\nl line 6: `$\#_{ai}$ $x_{ai}$', `$\#_{ai}$ $\alpha$' \becomes `$\#_{ri}$ $x_{ri}$', `$\#_{ri}$ $\alpha$' \endchange \amendpage 4b.468 append to answer 185 (23.08.10) (See OEIS sequence A113547 for other interpretations of these numbers.) \endchange \bugonpage 4b.485 line 12 (23.11.01) essentially unity \becomes essential unity \endchange \amendpage 4b.482 line $-4$ (22.11.25) 44 pages \becomes 46 pages \endchange \bugonpage 4b.497 replacement for answer 305{(a)} (23.02.04) \indent (a) Two cases: We can use a $5\times5$ box, and require that the small squares of each option are either $\{\.{34},\.{45}\}$, $\{\.{47},\.{56}\}$, $\{\.{76},\.{65}\}$, or $\{\.{63},\.{54}\}$; or a $6\times6$ box, with those small-square coordinates shifted by~\.{11}. For example, if we call the leftmost piece `\.0', its $5\times5$ options are `\.0 \.{35} \.{37} \.{34} \.{45}', `\.0 \.{57} \.{77} \.{47} \.{56}', `\.0 \.{53} \.{33} \.{63} \.{54}', `\.0 \.{75} \.{73} \.{76} \.{65}'. The $5\times5$ problem has $4\cdot183$ solutions, in groups of four that are related by $90^\circ$ rotation; the $6\times6$ problem, similarly, has $4\cdot209$ solutions. Reflection gives $4\cdot183+4\cdot209$ more. Here are some of the $8+5$ classes of equivalent solutions whose large squares form a symmetric shape; the last two of these look the same, but use different pieces(!): $$\def\\#1{\vcenter{\epsfbox{\figdir/v4b.331#1}}} \def\|#1{\vcenter{\epsfbox{\figdir/v4b.334#1}}} \def\epsfsize#1#2{.7#1} \kern-20pt\\0\quad\\1\!\!\quad\\2\quad\\4\quad\\5\quad\|6\ \|7\ \|8\kern-20pt$$ \endchange \amendpage 4b.498 and 499 in answer 306 (23.01.03) [change `snake-in-the-box' to simply `snake', in two places] \endchange \bugonpage 4b.498 and 499 in answer 306 (23.01.22) line 2: both even, and $00$. It's currently unknown whether or not exactly {\it five\/} loops are possible.] \endchange \improvepage 4b.536 line $-5$ of answer 413 (23.08.31) we unclose the loop (and set $\.E\gets0$) if $i=\.E$; otherwise we zero the mates and set \becomes we set $\.E\gets0$ (to unclose the loop), if $i=\.E$; but if $i\ne\.E$, we set $\.{MATE($u$)}\gets\.{MATE($v$)}\gets0$ and \endchange \bugonpage 4b.539 in answer 422 (22.12.31) line 1: $2m-2$ \becomes $2m-1$ \quad and\quad $2n-2$ \becomes $2n-1$\nl lines 9 and 10: $N(i,j)=C(1,j)-10$, \dots\ Edges \becomes $N(i,j)=C(i,j)-21$, $NN(i,j)=C(i,j)-41$, $W(i,j)=C(i,j)-12$, $WW(i,j)=C(i,j)-14$; $N(i,j)$ is the edge between cells $(i,j)$ and $(i-1,j)$. Edges \endchange \amendpage 4b.540 last lines of answer 425 (22.11.10) solutions for $k=5$ \dots\ 9, 10. \becomes solutions for $5\le k\le 10$, due to G.~J.~H. Goh, are also known. (See (xviii)--(xxiv) in Fig.~\fig A--5/; {\tt https://boonsuan.github.io/masyu.pdf}.) \endchange \amendpage 4b.548 replacement for copy after the display in answer 449 (23.10.22) \noindent Literary hitori nuggets longer than 80 characters were first reported by Gary McDonald in 2023: ($7\times12=84$) ``he stood and carefully examined the sky, to ascertain the time of night from the altitudes of the stars.'' [Thomas Hardy, {\sl Far from the Madding Crowd\/} (1874)]. ($11\times8=88$) ``\thinspace`\dots But talk to me of poverty and wealth, and there indeed we touch upon realities.' `My De-ar, this is becoming Awful\dash---'\thinspace'' [Charles Dickens, {\sl Our Mutual Friend\/} (1864)]. ($10\times10=100$) ``shall never forget his flying Henry's kite for him that very windy day last Easter\dash---and ever since his particular kindness'' [Jane Austen, {\sl Emma\/} (1816)]. \endchange \amendpage 4b.549 new answer (23.06.18) \ans5. The upper bound $W(3,k)=e^{O(\log k)^{11}}$ follows from (surprising) results of Z.~Kelley and R.~Meka, \arXiv:2302.05537 [math.NT], 79~pages. The (surprising) superpolynomial lower bound $W(3,k)=k^{\Omega(\log k/\log\log k)}$ was proved by B.~Green and Z.~Hunter in {\sl Forum of Mathematics, Pi\/ \bf10} (2022), e18:1--51; {\sl Combinatorica\/ \bf42} (2022), 1231--1252. \endchange \amendpage 4b.565 at end of answer 84 (24.01.10) There's no known way \dots\ for all $j\ge0$.] \becomes There's no known way to prove even the special cases that, say, $f^*(j,2j)=6j$ for all $j\ge0$. There has, however, been a recent spectacular breakthrough: As of February 2024, Tomas Rokicki has verified equality for all cells $(i,j)$ with $i\le6$ or $j\le6$.] \endchange \bugonpage 4b.611 line 6 of answer 318 (24.02.02) $g_n-g_{n+1}=p/g_n^t-p/g_{n+1}^t>0$ when $g_{n+1}0$ when $g_n%% Unicode char "845b \\\GC75:65:-3:60% G3302 <00000003e0000000000000000001f8000000000000000001fe000000000000000000ff00% 00000000000000007f0000000000000000007f8000000000000000003f80000000000000% 00001fc000000000000000001fc000000000000000000fc000000000000000000fc00000% 0000000000000fc0000780000000000007c0000fc000000000000400001fe00000000000% 0000003ff0000ffffffffffffffff80003fffffffffffffffc0001fffffffffffffffc00% 000000000000000000000000000000000000000000000000000000000000000000000000% 380000000000000000003e0000000000000000003f0000000000000000007fc000000000% 700000007fe000000000380000007fc0000000003c0000007f80000000001e0000007f80% 000000001f0000007f00000000000f0000007f00000000000f8000007e000000000007c0% 0000fe000000000007e00000fc000000000007f00000fc000000000003f80000fc000000% 000003f80000f8000000000001fc0001f8000000000001fc0001f0000000000001fe0001% f0000000000000fe0003f0000000000000ff0003e0000000000000ff0003e00000000000% 007f8003c00000000000007f8007c00000000000007f8007c00000000000007f80078000% 00000000003f800f800000000000003f800f000000000000003f800f000000000000003f% 801f000000000000003f801e000000000000003f003e000000000000001f003c00000000% 0000001e007c00000000000000180078000000000000001000f8000000000000000000f0% 000000000000000001e000001c000000000001e000003e000000000003c000007f000000% 000003c00000ff80ffffffffffffffffffc07fffffffffffffffffe03fffffffffffffff% ffe0>%% Unicode char "7acb \JC48:48:0:40% J5581 <00fc0000000000f80000000000f00000006000f0000000f000f0fffffff800f07ffffffc% 00f003c0000000f003c0000000f003c0000000f003c0000004f003c0000004f003c00000% 04fc03c006000cf603c00f000cf703ffff800cf383ffffc018f383c00f8018f3c3c00f00% 18f3c3c00f0038f183c00f0038f003cc0f0070f003c70f0070f003c38f00f0f003c1cf00% f0f003c1cf00e0f003c0cf0000f003c00f0000f003c00f0000f003cc0f0000f003c70f00% 00f003c38f0000f003c1cf0000f003c1cf0000f003c0cf0000f003c00f0000f003c00f00% 00f003c00f0000f001800f0000f000000f0000f000000f0000f000000f0000f000000f00% 00f000000f1800f000000f3c00f0fffffffe00f07fffffff00f000000000006000000000% >%% Unicode char "6046 ), 370, 395, 520, 523, 680. Green, Ben Joseph, 549. % 3rd Gr{\=\i}nbergs (= Grinberg), Emanuels Donats Fr{\=\i}drihs J\=anis, 582. % 3rd Guibert, Olivier Patrick Serge, 395, 523. % 3rd Hardy, Thomas, 548. % 3rd Head of a list, \see List heads. % 3rd Hexadecimal digits, extended past \.f, 73, 80, 484. % 3rd Hunter, Zachary William Saunders, 549. % 3rd Induced subgraphs, 63, 114, 145--146, 153, 183, 265, 436, 626. % 3rd $k$-clauses: $k$-ary clauses, 187, 231. % 3rd Keller, Michael, 132, 432, 494, 505. % 3rd Kelley, Alexander (= Zander) Wilson, 549. % 3rd Kint-Bruynseels, Ronald Odilon Bondewijn, 509. % 3rd Knightley, Henry, 548. % 3rd Knuth, Donald Ervin (\GC75:75:-3:62% G2463 <0000001f0000000000000000001ff8000000000000000007ff000000000000000003ff80% 00000000000000007f8000000000000000007f8000000000000000003f8000003c000000% 00003f8000007e00000000001f800000ff00000000000f800001ff00ffffffffffffffff% ff80ffffffffffffffffffc07fffffffffffffffffe03800000000000000000000000000% 00000000000000000000000070000000000078000000f800000000007f000001fc000000% 00007ffffffffe00000000007fffffffff00000000003ffffffffe00000000003f000000% fc00000000003f000000fc00000000003f000000fc00000000003f000000fc0000000000% 3f000000fc00000000003f000000fc00000000003f000000fc00000000003f000000fc00% 000000003ffffffffc00000000003ffffffffc00000000003ffffffffc00000000003f00% 0000fc00000000003f000000fc00000000003f000000fc00000001c03e0000000003c000% 01e03e0000000007e00001f800000000000ff00001fffffffffffffff00001ffffffffff% fffff80001f8000000000007f80001f8000000000007e00001f8000000000007e00001f8% 000000000007e00001f801c000078007e00001f801e00007e007e00001f801f8000ff007% e00001f801fffffff007e00001f801fffffff007e00001f801ffffffc007e00001f801f8% 000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e000% 01f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000f% c007e00001f801f8000fc007e00001f801ffffffc007e00001f801ffffffc007e00001f8% 01ffffffc007e00001f801f8000fc007e00001f801f0000fc007e00001f801f0000f0007% e00001f801f000000007e00001f8000000000007e00001f800000000ffcfe00001f80000% 00007fffc00001f8000000000fffc00001f80000000000ffc00001f800000000007f8000% 01f800000000003f800001f000000000001f000001f00000000000100000>%% Unicode char "9ad8 \GC73:74:-4:61% G2134 <00006000001c000000000000f000001f000000000000f800001fc00000000001fc00001f% e00000000001fe00001fe00000000003fe00001fc00000000003f800001fc00000000007% f000001f800070000007e000003f0000f800000fc000003f0001fc00001f8000007e0003% fe00001f07ffffffffffff00003e03ffffffffffff80007c0100007c0000000000f80000% 00780000000000f0000000780000000001e0000000700000000003c03838007000070000% 07807c3c00f0000f80001f007f3f00e0001f80003e00ffbfffffffffc0007c00ffbfffff% ffffe000f801ff1fffffffffe000c001fe1f03e0780f80000003fe1f03e0780f80000003% fc1f03e0780f80000007f81f03e0780f80000007f01f03e0780f8000000fe01f03e0780f% 8000000fc01f03e0780fc000001f801f03e0780fc000003f001f03e0780fc000003fe01f% 03e0780fc000007fe01f03e0780fc00000ffe01f03e0780fc00000ffc01fffffffffc000% 01ffc01fffffffffc00001ff803fffffffffc00001ff803f0000000f800003df803f0000% 000f8000079f803f0000000038000f9f803f000000007c001f1f800000000000fe003e1f% 800000000001ff007c1fbfffffffffffff80f81f9fffffffffffff80e01f880000000000% 0000801f8000003000000000001f8000001c00000000001f8000f01e00000000001f8000% fc0f001e0000001f8000ff0f801f0000001f8060ff07c00f8000001f8060ff07e00fe000% 001f8060fe03e007f000001f8060fc03e003f800001f8060fc03f003fc00001f80e0fc03% f0c1fe00001f81e0fc03f0c0ff00001f81e0fc03e0e0ff00001f83e0fc01e0e07f00001f% 83e0fc0000e07f00001f87e0fc0000e03f00001f9fe0fc0001f03f00001fbfe0fc0001f0% 1f00001fbfe0fc0003f01f00001f9fe0fe0003f81800001f9fc0fffffff80000001f8380% fffffff80000001f80007ffffff80000001f80003ffffff00000001f80001ffffff00000% 001f8000000000000000001f0000000000000000>%% Unicode char "5fb7 \GC71:74:-3:61% G3641 <000000000003800000000000000003f00000000300000003fc00000003c0000003fc0000% 0003e0000003f800000007f0000003f800000007f0000003f000000007e0000003f00000% 0007e0000003f000000007c0000003f00000000fc0000003f00000000f80000003f00000% 001f00000003e00000001f00000003e000e0003e00038003e001f0003e00c3e003e001f8% 007c00e1f803e003fc007800f1fffffffffe00f801f9fffffffffe00f001fdf003e003fc% 01e003fff003e003f801e007fff003e003f001c007fdf003e003f003800ff9f003e003f0% 03001ff1f003e003f00f003fe1f003e003f01e01ffc1f003e003f0ffffff81f003e003f0% ffffff01f003e003f07ffcfe01f007e003f07ff0fc01f007c003f03fc1f801f007c003f0% 3c01f001f007e003f00003e001f00ff003f00003c001f00ff803f00007c001f00ffc03f0% 000f8001f00f9e03f0001f0001f01f9f83f0001e0001f01f0fc3f0003e0001f01f07e3f0% 007c0001f03e07e3f000f80001f03e03f3f001f00001f03c03f3f007e00ff9f07c03fbf0% 0fc3fff9f07803fbf01fffffc1f0f801fbf01fffff01f0f001fbf00ffff001f1f001fbf0% 0ffc0001f1e001fbf007f00001f3c000fbf007c00001f30000fbf002000001f600007bf0% 00000001f4000003f000000001f4000003f000000001f0000003f000000001f0000003f0% 000003fff0000003f00001fffff0000003f000fffff1f0000003f07fffffe1f0000003f0% 7ffffc01f0000003f07fffe001f0000003f03fff8001f0000003f03ff00001f0000003f0% 3f800001f0000007f01e000001f0003c07f010000001f0000ffff000000001f00003fff0% 00000001f000007ff000000001f000003ff000000001f000001ff000000001f000001fc0% 00000003f000000f80000000000000000e00>%% Unicode char "7eb3 ), ii, iv, vi, viii, ix, xvii, 46, 54, 55, 63, 73, 77--79, 100, 118, 123, 185, 198, 200, 203, 235--236, 256, 258, 277, 278, 302, 309--311, 384, 389, 397, 401, 406, 412, 413, 419, 420, 424--425, 427, 429, 431--432, 440, 446, 459, 460, 463, 473, 475--478, 480, 481, 484, 485, 501--503, 508, 511, 514, 523, 527, 532, 533, 538, 540, 541, 544, 548, 556, 557, 559, 561, 566, 574, 576, 577, 580, 583, 584, 591, 599--601, 604, 606, 613, 624, 628--631, 638, 639, 642, 643, 646, 650, 654, 80, 686, 714. % 3rd List heads, 65--68, 89, 124, 212, 480. % 3rd Lubiw, Anna, 648. % 3rd Meka, Raghu Vardhan Reddy ({\tl \|0128|\C103\\1\|0128|\C74\C135\ \|1128|\C107\\2\|0128|\raise.1ex\hbox{\|0167|}\C103\\1\|1148|\C90\ \|0141|\C103\\2\raise.1ex\hbox{\|2161|}\|3131|\C83\ \|0142|\C101\|0128|\C71}), 549. % 3rd Model RB, 333--334. % 2nd Modifications of Algorithm 7\period2\period2\period1C and related algorithms, 126, 127, 132, 133, 138, 183, 422, 442, 445, 463, 542. % 3rd Multiple covering with colors, \see {\mc MCC} problem. % 3rd Oak, Gabriel, 548. % 3rd Octabytes, 534. % 3rd [because of reformatting pages 534--535] OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}), 422, 423, 455, 468, 469, 504, 516, 556, 647. % 3rd Online resources, \see Downloadable programs, Internet. % 3rd {\mc OR} operation, bitwise ($x\bor y$), 17, 128, 227, 410, 560, 605, 622--623. Pairwise ordering trick, 72, 126, 174, 420, 430, 463. % 3rd Pi day puzzle, 60, 411, 439. % 3rd Proof logging, \see Certificates of unsatisfiability. % 3rd Progress, display of, 73, 126, 214, 329, 339. % 3rd Propagation algorithm, 412. % 3rd Purcell, Michael, 370. % 3rd ${\cal Q}_n$ configuration, 145. % 3rd Ramakrishnan, Kajamalai Gopalaswamy\indexbreak ({\tm\\170\\127\\173\\127\\203\\126\\207\ \\125\\170\\127\\202\\127\\207\\302\\210\\127\\233\ \\205\\127\\203\\220\\315\\161\\176\\150}), 199. % 3rd RB random instances, 333--334. % 2nd Representation of sets, 534. % 3rd [because of reformatting pages 534--535] Reversible memory technique, 44, 59, 222. % 3rd Rodr{\'\i}guez Carbonell (= Rodr{\'\i}guez-Carbonell), Enric, 631. % 3rd Rokicki, Tomas\sic/ Gerhard, ix, 564, 565. % 3rd Rows of musical tones, 135. % 3rd Search trees, 31, 32, 35, 37--39, 46--48, 52, 54, 73, 98--100, 104--107, 126, 147, 212--213, 216--218, 239, 308, 336, 399, 406, 407, 412, 434. % 3rd Self-equivalent sudoku solutions, 111, 137. % 3rd Sequential lists, 39--43, 220--221, 328, 534. % 3rd [because of reformatting pages 534--535] Signature of a subproblem, 120--122, 154, 484. % 3rd Slack options, 71, 478. % 3rd Slack variables, 71. % 3rd Snake cycles, 146, 161, 465. % 3rd Snake paths, 145. % 3rd Stamp folding, 465. % 3rd Stappers, Filip Jan Jos, ix, 426, 431, 466, 533. % 3rd Stirling, partition numbers, 138, 234, 333, 423, 424, 468, 584, 590. % 3rd Sudoku, symmetries of, 74, 111, 137. % 3rd \sub with knights and bishops, 146. % 3rd Tagged vertices, 414. % 3rd Tetraboloes, 163. % 3rd Twintree structure, 172. % 3rd Two stacks, 534. % 3rd [because of reformatting pages 534--535] Unique solutions, 59, 75, 85, 128, 130--132, 140, 144, 146, 157, 160, 164, 173--183, 413, 453, 490--491, 502, 513, 514, 517, 519, 522, 535, 640. % 3rd Unmatchable (blank) color, 88--89, 463. % 3rd Utility fields in SGB format, 414. % 3rd Weigel, Peter Heinrich, 444, 509, 532. % 3rd Wilfer, Bella, 548. % 3rd Woodhouse, Emma, 548. % 3rd \vfill \enddoublecolumns \endchange \bugonpage 4b.714 line $-6$ (22.11.14) \eightpoint on an Dell Precision \becomes on a Dell Precision \endchange \bye [The next printing will be the 3rd.] not listed above: pages iv and viii, http: -> https: page 40, just before (22), (19) is in wrong font page 54, line 17, hyphenate Carnegie-Mellon page 54, line -18, add "in" page 59, add a period following display in exercise 64 page 176, line 1, I adjusted the spacing in `9\times' page 418, lines -7 to -4, (ref) -> [ref] page 463, line 12, inactivated -> deactivated page 528 changes to accommodate the change to page 529 page 533, similar spacing adjustments as on page 176 page 540, line -3 when -> when we have page 572 and 573, bigger asterisks in Algorithm 7.2.2.2 A* page 589, line -3 of answer 214, Probability and Computing page 666, asterisk in Algorithm 7.2.2.2A* page 674, adjusted spacing slightly in the epsilon entries Bloom, Thomas Frederick, leaves the index L-cube puzzle leaves the index Solid bent trominoes leaves the index The change to page 411 affects also pages 412, 413, 414, 415 The change to page 432 affects also pages 433, 434, 435 The change to page 497 affects also page 496 Shlyakhter leaves the index ARTICLES "TO APPEAR" THAT ARE STILL PENDING: Simkin arXiv 2107.13460 [ans 7.2.2--15] Green in Forum of Math (ans 7.2.2.2--5) Hunter in Combinatorica (ans 7.2.2.2--5) Kelley and Meka (ans 7.2.2.2--5) surely will also be published