% CHANGES TO VOLUME 4B OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2022, 2023 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
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.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
\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
\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.135 lines 8 and 9 of exercise 103 (23.01.03)
\ninepoint twelve-tone row \becomes {\it twelve-tone row}
\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
\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.160 new rating for exercise 305 (23.02.03)
\ninepoint {\it 25\/} \becomes {\it 28}
\endchange
\amendpage 4b.160 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.459 line 13 of answer 151 (22.11.05)
with Algorithm X \becomes with Algorithm X and exercise 413
\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 4: 6 T$\mu$ \becomes 270 G$\mu$\nl
line 8: 13 M$\mu$ \becomes 54 M$\mu$\nl
line 12: (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 17: 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 the last paragraph (23.02.02)
\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.01.03)
Nikolai \dots\ [To appear.] \becomes\nl
\indent Nikolai Beluhov has shown that the maximum length of an $n\times n$
snake king path is $\lceil n^2\!/2\rceil-1$. Indeed, those longest 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.\par
With arguments of a different kind, 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 \arXiv:2301.01152 [math.CO] (2023), 36~pages.]
\endchange
\amendpage 4b.482 line $-4$ (22.11.25)
44 pages \becomes 46 pages
\endchange
\bugonpage 4b.497 replacement for answer 306{(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 $0%% 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, 466, 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
Model RB, 333--334. % 2nd
Moody, Alastor, 548. % 3rd
{\mc OR} operation, bitwise ($x\bor y$), 17, 128, 227, 410, 560, 605, 622--623.
Pi day puzzle, 60, 411, 439. % 3rd
Potter, Harry James, 548. % 3rd
Proof logging, \see Certificates of unsatisfiability. % 3rd
Propagation algorithm, 412. % 3rd
RB random instances, 333--334. % 2nd
Rowling, Joanne (= J\period\ K\period), 548.
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
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, 533, 548. % 3rd
Sudoku, symmetries of, 74, 111, 137. % 3rd
Tagged vertices, 414. % 3rd
Tetraboloes, 163. % 3rd
Twintree structure, 172. % 3rd
Utility fields in SGB format, 414. % 3rd
Weigel, Peter Heinrich, 444, 509, 532. % 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:
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 533, similar spacing adjustments as on page 176
page 674, adjusted spacing slightly in the epsilon entries
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 497 affects also page 496
Apge 540, line -3 when -> when we have
ARTICLES "TO APPEAR" THAT ARE STILL PENDING:
Simkin arXiv 2107.13460 [ans 7.2.2--15]
Nobel,Agrawal,Boyd arXiv 2112.03336 about Simkin's constant [ans 7.2.2--15]