\input cwebmac
\let\Xmod=\bmod % this is CWEB magic for using "mod" instead of "%"

\datethis

\N{1}{1}Intro. This program is part of a series of ``exact cover solvers'' that
I'm putting together for my own education as I prepare to write Section
7.2.2.1 of {\sl The Art of Computer Programming}. My intent is to
have a variety of compatible programs on which I can run experiments,
in order to learn how different approaches work in practice.

Indeed, this is the first of the series.
I've tried to write it as a primitive baseline against which I'll be able
to measure various technical improvements and extensions.
{\mc DLX1} is based on the program {\mc DANCE}, which I wrote hastily
in 1999 while preparing my paper about ``Dancing Links.'' [See
{\sl Selected Papers on Fun and Games\/} (2011), Chapter~38, for a
revised version of that paper, which first appeared in the book
{\sl Millennial Perspectives in Computer Science\/}, a festschrift
for C.~A.~R. Hoare (2000).] That program, incidentally, was based
on a program called {\mc XCOVER} that I first wrote in 1994.
After using {\mc DANCE} as a workhorse
for more than 15 years, and after extending it in dozens of ways
for a wide variety of combinatorial problems, I'm finally ready to replace it
with a more carefully crafted piece of code.

My intention is to make this program match Algorithm 7.2.2.1X, so that
I~can use it to make the quantitative experiments that will ultimately
be reported in Volume~4B.

Although this is the entry-level program, I'm taking care to adopt conventions
for input and output that will be essentially the same (or at least
backward compatible) in all of the fancier versions that are to come.

We're given a matrix of 0s and 1s, whose columns represent ``items''
and whose rows represent ``options.'' Some of the items are called
``primary'' while the others are ``secondary.''
Every option contains a~1 for at least one primary item.
The problem is to find all subsets of the options whose sum is
(i)~{\it exactly\/}~1 for all primary items;
(ii)~{\it at most\/}~1 for all secondary items.

This matrix, which is typically very sparse, is specified on \PB{\\{stdin}}
as follows:
\smallskip\item{$\bullet$} Each item has a symbolic name,
from one to eight characters long. Each of those characters can
be any nonblank ASCII code except for `\.{:}' and~`\.{\char"7C}'.
\smallskip\item{$\bullet$} The first line of input contains the
names of all primary items, separated by one or more spaces,
followed by `\.{\char"7C}', followed by the names of all other items.
(If all items are primary, the~`\.{\char"7C}' may be omitted.)
\smallskip\item{$\bullet$} The remaining lines represent the options,
by listing the items where 1~appears.
\smallskip\item{$\bullet$} Additionally, ``comment'' lines can be
interspersed anywhere in the input. Such lines, which begin with
`\.{\char"7C}', are ignored by this program, but they are often
useful within stored files.
\smallskip\noindent
Later versions of this program solve more general problems by
making further use of the reserved characters `\.{:}' and~`\.{\char"7C}'
to allow additional kinds of input.

For example, if we consider the matrix
$$\pmatrix{0&0&1&0&1&1&0\cr 1&0&0&1&0&0&1\cr 0&1&1&0&0&1&0\cr
1&0&0&1&0&0&0\cr 0&1&0&0&0&0&1\cr 0&0&0&1&1&0&1\cr}$$
which was (3) in my original paper, we can name the items
\.A, \.B, \.C, \.D, \.E, \.F,~\.G. Suppose the first five are
primary, and the latter two are secondary. That matrix can be
represented by the lines
$$
\vcenter{\halign{\tt#\cr
\char"7C\ A simple example\cr
A B C D E \char"7C\ F G\cr
C E F\cr
A D G\cr
B C F\cr
A D\cr
B G\cr
D E G\cr}}
$$
(and also in many other ways, because item names can be given in
any order, and so can the individual options). It has a unique solution,
consisting of the three options \.{A D} and \.{E F C} and \.{B G}.

\fi

\M{2}After this program finds all solutions, it normally prints their total
number on \PB{\\{stderr}}, together with statistics about how many
nodes were in the search tree, and how many ``updates'' were made.
The running time in ``mems'' is also reported, together with the approximate
number of bytes needed for data storage. One ``mem'' essentially means a
memory access to a 64-bit word.
(These totals don't include the time or space needed to parse the
input or to format the output.)

Here is the overall structure:

\Y\B\4\D\|o\5
$\\{mems}\PP{}$\C{ count one mem }\par
\B\4\D\\{oo}\5
$\\{mems}\MRL{+{\K}}{}$\T{2}\C{ count two mems }\par
\B\4\D\\{ooo}\5
$\\{mems}\MRL{+{\K}}{}$\T{3}\C{ count three mems }\par
\B\4\D\|O\5
\.{"\%"}\C{ used for percent signs in format strings }\par
\B\4\D\Xmod\5
$\MOD{}$\C{ used for percent signs denoting remainder in \CEE/ }\par
\B\4\D\\{max\_level}\5
\T{10000}\C{ at most this many options in a solution }\par
\B\4\D\\{max\_cols}\5
\T{100000}\C{ at most this many items }\par
\B\4\D\\{max\_nodes}\5
\T{25000000}\C{ at most this many nonzero elements in the matrix }\par
\B\4\D\\{bufsize}\5
$(\T{9}*\\{max\_cols}+\T{3}{}$)\C{ a buffer big enough to hold all item names }%
\par
\Y\B\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{<stdlib.h>}\6
\8\#\&{include} \.{<string.h>}\6
\8\#\&{include} \.{<ctype.h>}\6
\8\#\&{include} \.{"gb\_flip.h"}\6
\&{typedef} \&{unsigned} \&{int} \&{uint};\C{ a convenient abbreviation }\6
\&{typedef} \&{unsigned} \&{long} \&{long} \&{ullng};\C{ ditto }\7
\X6:Type definitions\X;\6
\X3:Global variables\X;\6
\X10:Subroutines\X;\7
\\{main}(\&{int} \\{argc}${},\39{}$\&{char} ${}{*}\\{argv}[\,]){}$\1\1\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \\{cc}${},{}$ \|i${},{}$ \|j${},{}$ \|k${},{}$ \|p${},{}$ %
\\{pp}${},{}$ \|q${},{}$ \|r${},{}$ \|t${},{}$ \\{cur\_node}${},{}$ \\{best%
\_itm};\7
\X4:Process the command line\X;\6
\X14:Input the item names\X;\6
\X17:Input the options\X;\6
\&{if} ${}(\\{vbose}\AND\\{show\_basics}){}$\1\5
\X21:Report the successful completion of the input phase\X;\2\6
\&{if} ${}(\\{vbose}\AND\\{show\_tots}){}$\1\5
\X22:Report the item totals\X;\2\6
${}\\{imems}\K\\{mems},\39\\{mems}\K\T{0};{}$\6
\X23:Solve the problem\X;\6
\4\\{done}:\5
\&{if} ${}(\\{vbose}\AND\\{show\_tots}){}$\1\5
\X22:Report the item totals\X;\2\6
\&{if} ${}(\\{vbose}\AND\\{show\_profile}){}$\1\5
\X35:Print the profile\X;\2\6
\&{if} ${}(\\{vbose}\AND\\{show\_max\_deg}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"The\ maximum\ branchi}\)\.{ng\ degree\ was\ "}%
\|O\.{"d.\\n"},\39\\{maxdeg});{}$\2\6
\&{if} ${}(\\{vbose}\AND\\{show\_basics}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Altogether\ "}\|O\.{"llu\ solution"}\|O\.{"s,\
"}\|O\.{"llu+"}\|O\.{"llu\ mems,"},\39\\{count},\39\\{count}\E\T{1}\?\.{""}:%
\.{"s"},\39\\{imems},\39\\{mems});{}$\6
${}\\{bytes}\K\\{last\_itm}*\&{sizeof}(\&{item})+\\{last\_node}*\&{sizeof}(%
\&{node})+\\{maxl}*\&{sizeof}(\&{int});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{"llu\ updates,\ "}\|O\.{"llu\ bytes,%
\ "}\|O\.{"llu\ nodes,"},\39\\{updates},\39\\{bytes},\39\\{nodes});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"\ ccost\ "}\|O\.{"lld\%\%.\\n"},\39(\T{200}*%
\\{cmems}+\\{mems})/(\T{2}*\\{mems}));{}$\6
\4${}\}{}$\2\6
\X5:Close the files\X;\6
\4${}\}{}$\2\par
\fi

\M{3}You can control the amount of output, as well as certain properties
of the algorithm, by specifying options on the command line:
\smallskip\item{$\bullet$}
`\.v$\langle\,$integer$\,\rangle$' enables or disables various kinds of verbose
output on \PB{\\{stderr}}, given by binary codes such as \PB{\\{show%
\_choices}};
\item{$\bullet$}
`\.m$\langle\,$integer$\,\rangle$' causes every $m$th solution
to be output (the default is \.{m0}, which merely counts them);
\item{$\bullet$}
`\.s$\langle\,$integer$\,\rangle$' causes the algorithm to make
random choices in key places (thus providing some variety, although
the solutions are by no means uniformly random), and it also
defines the seed for any random numbers that are used;
\item{$\bullet$}
`\.d$\langle\,$integer$\,\rangle$' sets \PB{\\{delta}}, which causes periodic
state reports on \PB{\\{stderr}} after the algorithm has performed
approximately
\PB{\\{delta}} mems since the previous report (default 10000000000);
\item{$\bullet$}
`\.c$\langle\,$positive integer$\,\rangle$' limits the levels on which
choices are shown during verbose tracing;
\item{$\bullet$}
`\.C$\langle\,$positive integer$\,\rangle$' limits the levels on which
choices are shown in the periodic state reports;
\item{$\bullet$}
`\.l$\langle\,$nonnegative integer$\,\rangle$' gives a {\it lower\/} limit,
relative to the maximum level so far achieved, to the levels on which
choices are shown during verbose tracing;
\item{$\bullet$}
`\.t$\langle\,$positive integer$\,\rangle$' causes the program to
stop after this many solutions have been found;
\item{$\bullet$}
`\.T$\langle\,$integer$\,\rangle$' sets \PB{\\{timeout}} (which causes abrupt
termination if \PB{$\\{mems}>\\{timeout}$} at the beginning of a level);
\item{$\bullet$}
`\.S$\langle\,$filename$\,\rangle$' to output a ``shape file'' that encodes
the search tree.

\Y\B\4\D\\{show\_basics}\5
\T{1}\C{ \PB{\\{vbose}} code for basic stats; this is the default }\par
\B\4\D\\{show\_choices}\5
\T{2}\C{ \PB{\\{vbose}} code for backtrack logging }\par
\B\4\D\\{show\_details}\5
\T{4}\C{ \PB{\\{vbose}} code for further commentary }\par
\B\4\D\\{show\_profile}\5
\T{128}\C{ \PB{\\{vbose}} code to show the search tree profile }\par
\B\4\D\\{show\_full\_state}\5
\T{256}\C{ \PB{\\{vbose}} code for complete state reports }\par
\B\4\D\\{show\_tots}\5
\T{512}\C{ \PB{\\{vbose}} code for reporting item totals at start and end }\par
\B\4\D\\{show\_warnings}\5
\T{1024}\C{ \PB{\\{vbose}} code for reporting options without primaries }\par
\B\4\D\\{show\_max\_deg}\5
\T{2048}\C{ \PB{\\{vbose}} code for reporting maximum branching degree }\par
\Y\B\4\X3:Global variables\X${}\E{}$\6
\&{int} \\{random\_seed}${}\K\T{0}{}$;\C{ seed for the random words of \PB{%
\\{gb\_rand}} }\6
\&{int} \\{randomizing};\C{ has `\.s' been specified? }\6
\&{int} \\{vbose}${}\K\\{show\_basics}+\\{show\_warnings}{}$;\C{ level of
verbosity }\6
\&{int} \\{spacing};\C{ solution $k$ is output if $k$ is a multiple of \PB{%
\\{spacing}} }\6
\&{int} \\{show\_choices\_max}${}\K\T{1000000}{}$;\C{ above this level, \PB{%
\\{show\_choices}} is ignored }\6
\&{int} \\{show\_choices\_gap}${}\K\T{1000000}{}$;\C{ below level \PB{$%
\\{maxl}-\\{show\_choices\_gap}$},     \PB{\\{show\_details}} is ignored }\6
\&{int} \\{show\_levels\_max}${}\K\T{1000000}{}$;\C{ above this level, state
reports stop }\6
\&{int} \\{maxl}${}\K\T{0}{}$;\C{ maximum level actually reached }\6
\&{char} \\{buf}[\\{bufsize}];\C{ input buffer }\6
\&{ullng} \\{count};\C{ solutions found so far }\6
\&{ullng} \\{options};\C{ options seen so far }\6
\&{ullng} \\{imems}${},{}$ \\{mems}${},{}$ \\{cmems}${},{}$ \\{tmems};\C{ mem
counts }\6
\&{ullng} \\{updates};\C{ update counts }\6
\&{ullng} \\{bytes};\C{ memory used by main data structures }\6
\&{ullng} \\{nodes};\C{ total number of branch nodes initiated }\6
\&{ullng} \\{thresh}${}\K\T{10000000000}{}$;\C{ report when \PB{\\{mems}}
exceeds this, if \PB{$\\{delta}\I\T{0}$} }\6
\&{ullng} \\{delta}${}\K\T{10000000000}{}$;\C{ report every \PB{\\{delta}} or
so mems }\6
\&{ullng} \\{maxcount}${}\K\T{\^ffffffffffffffff}{}$;\C{ stop after finding
this many solutions }\6
\&{ullng} \\{timeout}${}\K\T{\^1fffffffffffffff}{}$;\C{ give up after this many
mems }\6
\&{FILE} ${}{*}\\{shape\_file}{}$;\C{ file for optional output of search tree
shape }\6
\&{char} ${}{*}\\{shape\_name}{}$;\C{ its name }\6
\&{int} \\{maxdeg};\C{ the largest branching degree seen so far }\par
\As8\ET24.
\U2.\fi

\M{4}If an option appears more than once on the command line, the first
appearance takes precedence.

\Y\B\4\X4:Process the command line\X${}\E{}$\6
\&{for} ${}(\|j\K\\{argc}-\T{1},\39\|k\K\T{0};{}$ \|j; ${}\|j\MM){}$\1\6
\&{switch} (\\{argv}[\|j][\T{0}])\5
${}\{{}$\1\6
\4\&{case} \.{'v'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{vbose})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'m'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{spacing})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'s'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{random\_seed})-\T{1}),\39\\{randomizing}\K\T{1}{}$;\5
\&{break};\6
\4\&{case} \.{'d'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"lld"},\39{%
\AND}\\{delta})-\T{1}),\39\\{thresh}\K\\{delta}{}$;\5
\&{break};\6
\4\&{case} \.{'c'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{show\_choices\_max})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'C'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{show\_levels\_max})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'l'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"d"},\39{%
\AND}\\{show\_choices\_gap})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'t'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"lld"},\39{%
\AND}\\{maxcount})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'T'}:\5
${}\|k\MRL{{\OR}{\K}}(\\{sscanf}(\\{argv}[\|j]+\T{1},\39\.{""}\|O\.{"lld"},\39{%
\AND}\\{timeout})-\T{1}){}$;\5
\&{break};\6
\4\&{case} \.{'S'}:\5
${}\\{shape\_name}\K\\{argv}[\|j]+\T{1},\39\\{shape\_file}\K\\{fopen}(\\{shape%
\_name},\39\.{"w"});{}$\6
\&{if} ${}(\R\\{shape\_file}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ I\ can't\ open}\)\.{\ file\ `"}\|O%
\.{"s'\ for\ writing!\\n"},\39\\{shape\_name});{}$\2\6
\&{break};\6
\4\&{default}:\5
${}\|k\K\T{1}{}$;\C{ unrecognized command-line option }\6
\4${}\}{}$\2\2\6
\&{if} (\|k)\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Usage:\ "}\|O\.{"s\ [v<n>]\ [m<n>]\ [s<}\)%
\.{n>]\ [d<n>]"}\.{"\ [c<n>]\ [C<n>]\ [l<n}\)\.{>]\ [t<n>]\ [T<n>]\ [S<}\)%
\.{bar>]\ <\ foo.dlx\\n"},\39\\{argv}[\T{0}]);{}$\6
${}\\{exit}({-}\T{1});{}$\6
\4${}\}{}$\2\6
\&{if} (\\{randomizing})\1\5
\\{gb\_init\_rand}(\\{random\_seed});\2\par
\U2.\fi

\M{5}\B\X5:Close the files\X${}\E{}$\6
\&{if} (\\{shape\_file})\1\5
\\{fclose}(\\{shape\_file});\2\par
\U2.\fi

\N{1}{6}Data structures.
Each item of the input matrix is represented by an \&{item} struct,
and each option is represented as a list of \&{node} structs. There's one
node for each nonzero entry in the matrix.

More precisely, the nodes of individual options appear sequentially,
with ``spacer'' nodes between them. The nodes are also
linked circularly with respect to each item, in doubly linked lists.
The item lists each include a header node, but the option lists do not.
Item header nodes are aligned with an \&{item} struct, which
contains further info about the item.

Each node contains three important fields. Two are the pointers \PB{\\{up}}
and \PB{\\{down}} of doubly linked lists, already mentioned.
The third points directly to the item containing the node.

A ``pointer'' is an array index, not a \CEE/ reference (because the latter
would occupy 64~bits and waste cache space). The \PB{\\{cl}} array is for
\&{item} structs, and the \PB{\\{nd}} array is for \&{node}s. I assume that
both of
those arrays are small enough to be allocated statically. (Modifications
of this program could do dynamic allocation if needed.)
The header node corresponding to \PB{\\{cl}[\|c]} is \PB{\\{nd}[\|c]}.

We count one mem for a simultaneous access to the \PB{\\{up}} and \PB{\\{down}}
fields.
I've added a \PB{\\{spare}} field, so that each \&{node} occupies two
octabytes.

Although the item-list pointers are called \PB{\\{up}} and \PB{\\{down}}, they
need not
correspond to actual positions of matrix entries. The elements of
each item list can appear in any order, so that one option
needn't be consistently ``above'' or ``below'' another. Indeed, when
\PB{\\{randomizing}} is set, we intentionally scramble each item list.

This program doesn't change the \PB{\\{itm}} fields after they've first been
set up.
But the \PB{\\{up}} and \PB{\\{down}} fields will be changed frequently,
although preserving
relative order.

Exception: In the node \PB{\\{nd}[\|c]} that is the header for the list of
item~\PB{\|c}, we use the \PB{\\{itm}} field to hold the {\it length\/} of that
list (excluding the header node itself).
We also might use its \PB{\\{spare}} field for special purposes.
The alternative names \PB{\\{len}} for \PB{\\{itm}} and \PB{\\{aux}} for \PB{%
\\{spare}}
are used in the code so that this nonstandard semantics will be more clear.

A {\it spacer\/} node has \PB{$\\{itm}\Z\T{0}$}. Its \PB{\\{up}} field points
to the start
of the preceding option; its \PB{\\{down}} field points to the end of the
following option.
Thus it's easy to traverse an option circularly, in either direction.

If all options have length \PB{\|m}, we can do without the spacers by simply
working modulo~\PB{\|m}. But the majority of my applications have options of
variable length, so I've decided not to use that trick.

[{\it Historical note:\/} An earlier version of this program, {\mc DLX0},
was almost identical to this one except that it used doubly linked lists
for the options as well as for the items. Thus it had two additional
fields, \PB{\\{left}} and \PB{\\{right}}, in each node. When I wrote {\mc DLX1}
I expected
it to be a big improvement, because I thought there would be fewer memory
accesses in all of the inner loops where options are being traversed. However,
I~failed to realize that the \PB{\\{itm}} and \PB{\\{right}} fields were both
stored in the
same octabyte; hence the cost per node is the same---and
{\mc DLX1} actually performs a few {\it more\/} mems, as
it handles the spacer node transitions! This additional mem cost is
compensated by the smaller node size, hence greater likelihood of cache hits.
But the gain from pure sequential allocation wasn't as great as I'd hoped.]

\Y\B\4\D\\{len}\5
\\{itm}\C{ item list length (used in header nodes only) }\par
\B\4\D\\{aux}\5
\\{spare}\C{ an auxiliary quantity (used in header nodes only) }\par
\Y\B\4\X6:Type definitions\X${}\E{}$\6
\&{typedef} \&{struct} \&{node\_struct} ${}\{{}$\1\6
\&{int} \\{up}${},{}$ \\{down};\C{ predecessor and successor in item list }\6
\&{int} \\{itm};\C{ the item containing this node }\6
\&{int} \\{spare};\C{ padding, not used in {\mc DLX1} }\2\6
${}\}{}$ \&{node};\par
\A7.
\U2.\fi

\M{7}Each \&{item} struct contains three fields:
The \PB{\\{name}} is the user-specified identifier;
\PB{\\{next}} and \PB{\\{prev}} point to adjacent items, when this
item is part of a doubly linked list.

As backtracking proceeds, nodes
will be deleted from item lists when their option has been hidden by
other options in the partial solution.
But when backtracking is complete, the data structures will be
restored to their original state.

We count one mem for a simultaneous access to the \PB{\\{prev}} and \PB{%
\\{next}} fields.

\Y\B\4\X6:Type definitions\X${}\mathrel+\E{}$\6
\&{typedef} \&{struct} \&{itm\_struct} ${}\{{}$\1\6
\&{char} \\{name}[\T{8}];\C{ symbolic identification of the item, for printing
}\6
\&{int} \\{prev}${},{}$ \\{next};\C{ neighbors of this item }\2\6
${}\}{}$ \&{item};\par
\fi

\M{8}\B\X3:Global variables\X${}\mathrel+\E{}$\6
\&{node} \\{nd}[\\{max\_nodes}];\C{ the master list of nodes }\6
\&{int} \\{last\_node};\C{ the first node in \PB{\\{nd}} that's not yet used }\6
\&{item} ${}\\{cl}[\\{max\_cols}+\T{2}]{}$;\C{ the master list of items }\6
\&{int} \\{second}${}\K\\{max\_cols}{}$;\C{ boundary between primary and
secondary items }\6
\&{int} \\{last\_itm};\C{ the first item in \PB{\\{cl}} that's not yet used }%
\par
\fi

\M{9}One \PB{\&{item}} struct is called the root. It serves as the head of the
list of items that need to be covered, and is identifiable by the fact
that its \PB{\\{name}} is empty.

\Y\B\4\D\\{root}\5
\T{0}\C{ \PB{\\{cl}[\\{root}]} is the gateway to the unsettled items }\par
\fi

\M{10}An option is identified not by name but by the names of the items it
contains.
Here is a routine that prints an option, given a pointer to any of its
nodes. It also prints the position of the option in its item list.

\Y\B\4\X10:Subroutines\X${}\E{}$\6
\1\1\&{void} \\{print\_option}(\&{int} \|p${},\39{}$\&{FILE} ${}{*}\\{stream})%
\2\2{}$\6
${}\{{}$\1\6
\&{register} \&{int} \|k${},{}$ \|q;\7
\&{if} ${}(\|p<\\{last\_itm}\V\|p\G\\{last\_node}\V\\{nd}[\|p].\\{itm}\Z%
\T{0}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Illegal\ option\ "}\|O\.{"d!\\n"},\39\|p);{}$\6
\&{return};\6
\4${}\}{}$\2\6
\&{for} ${}(\|q\K\|p;{}$  ; \,)\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stream},\39\.{"\ "}\|O\.{".8s"},\39\\{cl}[\\{nd}[\|q].%
\\{itm}].\\{name});{}$\6
${}\|q\PP;{}$\6
\&{if} ${}(\\{nd}[\|q].\\{itm}\Z\T{0}){}$\1\5
${}\|q\K\\{nd}[\|q].\\{up}{}$;\C{ \PB{${-}\\{nd}[\|q].\\{itm}$} is actually the
option number }\2\6
\&{if} ${}(\|q\E\|p){}$\1\5
\&{break};\2\6
\4${}\}{}$\2\6
\&{for} ${}(\|q\K\\{nd}[\\{nd}[\|p].\\{itm}].\\{down},\39\|k\K\T{1};{}$ ${}\|q%
\I\|p;{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|q\E\\{nd}[\|p].\\{itm}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stream},\39\.{"\ (?)\\n"}){}$;\5
\&{return};\C{ option not in its item list! }\6
\4${}\}{}$\5
\2\&{else}\1\5
${}\|q\K\\{nd}[\|q].\\{down};{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stream},\39\.{"\ ("}\|O\.{"d\ of\ "}\|O\.{"d)\\n"},\39\|k,\39%
\\{nd}[\\{nd}[\|p].\\{itm}].\\{len});{}$\6
\4${}\}{}$\2\7
\1\1\&{void} \\{prow}(\&{int} \|p)\2\2\6
${}\{{}$\1\6
${}\\{print\_option}(\|p,\39\\{stderr});{}$\6
\4${}\}{}$\2\par
\As11, 12, 26, 27, 33\ETs34.
\U2.\fi

\M{11}When I'm debugging, I might want to look at one of the current item
lists.

\Y\B\4\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{print\_itm}(\&{int} \|c)\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \|p;\7
\&{if} ${}(\|c<\\{root}\V\|c\G\\{last\_itm}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Illegal\ item\ "}\|O\.{"d!\\n"},\39\|c);{}$\6
\&{return};\6
\4${}\}{}$\2\6
\&{if} ${}(\|c<\\{second}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Item\ "}\|O\.{".8s,\ length\ "}\|O\.{"d,\
neighbors\ "}\|O\.{".8s\ and\ "}\|O\.{".8s:\\n"},\39\\{cl}[\|c].\\{name},\39%
\\{nd}[\|c].\\{len},\39\\{cl}[\\{cl}[\|c].\\{prev}].\\{name},\39\\{cl}[\\{cl}[%
\|c].\\{next}].\\{name});{}$\2\6
\&{else}\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Item\ "}\|O\.{".8s,\ length\ "}\|O\.{"d:\\n"},%
\39\\{cl}[\|c].\\{name},\39\\{nd}[\|c].\\{len});{}$\2\6
\&{for} ${}(\|p\K\\{nd}[\|c].\\{down};{}$ ${}\|p\G\\{last\_itm};{}$ ${}\|p\K%
\\{nd}[\|p].\\{down}){}$\1\5
\\{prow}(\|p);\2\6
\4${}\}{}$\2\par
\fi

\M{12}Speaking of debugging, here's a routine to check if redundant parts of
our
data structure have gone awry.

\Y\B\4\D\\{sanity\_checking}\5
\T{0}\C{ set this to 1 if you suspect a bug }\par
\Y\B\4\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{sanity}(\&{void})\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \|k${},{}$ \|p${},{}$ \|q${},{}$ \\{pp}${},{}$ %
\\{qq}${},{}$ \|t;\7
\&{for} ${}(\|q\K\\{root},\39\|p\K\\{cl}[\|q].\\{next};{}$  ; ${}\|q\K\|p,\39%
\|p\K\\{cl}[\|p].\\{next}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{cl}[\|p].\\{prev}\I\|q){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Bad\ prev\ field\ at\ i}\)\.{tm\ "}\|O\.{".8s!%
\\n"},\39\\{cl}[\|p].\\{name});{}$\2\6
\&{if} ${}(\|p\E\\{root}){}$\1\5
\&{break};\2\6
\X13:Check item \PB{\|p}\X;\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M{13}\B\X13:Check item \PB{\|p}\X${}\E{}$\6
\&{for} ${}(\\{qq}\K\|p,\39\\{pp}\K\\{nd}[\\{qq}].\\{down},\39\|k\K\T{0};{}$  ;
${}\\{qq}\K\\{pp},\39\\{pp}\K\\{nd}[\\{pp}].\\{down},\39\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{nd}[\\{pp}].\\{up}\I\\{qq}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Bad\ up\ field\ at\ nod}\)\.{e\ "}\|O\.{"d!%
\\n"},\39\\{pp});{}$\2\6
\&{if} ${}(\\{pp}\E\|p){}$\1\5
\&{break};\2\6
\&{if} ${}(\\{nd}[\\{pp}].\\{itm}\I\|p){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Bad\ itm\ field\ at\ no}\)\.{de\ "}\|O\.{"d!%
\\n"},\39\\{pp});{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{nd}[\|p].\\{len}\I\|k){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Bad\ len\ field\ in\ it}\)\.{em\ "}\|O\.{".8s!%
\\n"},\39\\{cl}[\|p].\\{name}){}$;\2\par
\U12.\fi

\N{1}{14}Inputting the matrix. Brute force is the rule in this part of the
code,
whose goal is to parse and store the input data and to check its validity.

\Y\B\4\D\\{panic}$(\|m)$\6
${}\{{}$\5
\1${}\\{fprintf}(\\{stderr},\39\.{""}\|O\.{"s!\\n"}\|O\.{"d:\ "}\|O\.{".99s%
\\n"},\39\|m,\39\|p,\39\\{buf}){}$;\5
${}\\{exit}({-}\T{666}){}$;\5
${}\}{}$\2\par
\Y\B\4\X14:Input the item names\X${}\E{}$\6
\&{if} ${}(\\{max\_nodes}\Z\T{2}*\\{max\_cols}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Recompile\ me:\ max\_n}\)\.{odes\ must\ exceed%
\ twi}\)\.{ce\ max\_cols!\\n"});{}$\6
${}\\{exit}({-}\T{999});{}$\6
\4${}\}{}$\C{ every item will want a header node and at least one other node }%
\2\6
\&{while} (\T{1})\5
${}\{{}$\1\6
\&{if} ${}(\R\\{fgets}(\\{buf},\39\\{bufsize},\39\\{stdin})){}$\1\5
\&{break};\2\6
\&{if} ${}(\|o,\39\\{buf}[\|p\K\\{strlen}(\\{buf})-\T{1}]\I\.{'\\n'}){}$\1\5
\\{panic}(\.{"Input\ line\ way\ too\ }\)\.{long"});\2\6
\&{for} ${}(\|p\K\T{0};{}$ \|o${},\39\\{isspace}(\\{buf}[\|p]);{}$ ${}\|p%
\PP){}$\1\5
;\2\6
\&{if} ${}(\\{buf}[\|p]\E\.{'|'}\V\R\\{buf}[\|p]){}$\1\5
\&{continue};\C{ bypass comment or blank line }\2\6
${}\\{last\_itm}\K\T{1};{}$\6
\&{break};\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{last\_itm}){}$\1\5
\\{panic}(\.{"No\ items"});\2\6
\&{for} ( ; \|o${},\39\\{buf}[\|p];{}$ \,)\5
${}\{{}$\1\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\T{8}\W(\|o,\39\R\\{isspace}(\\{buf}[\|p+%
\|j]));{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{buf}[\|p+\|j]\E\.{':'}\V\\{buf}[\|p+\|j]\E\.{'|'}){}$\1\5
\\{panic}(\.{"Illegal\ character\ i}\)\.{n\ item\ name"});\2\6
${}\|o,\39\\{cl}[\\{last\_itm}].\\{name}[\|j]\K\\{buf}[\|p+\|j];{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\|j\E\T{8}\W\R\\{isspace}(\\{buf}[\|p+\|j])){}$\1\5
\\{panic}(\.{"Item\ name\ too\ long"});\2\6
\X15:Check for duplicate item name\X;\6
\X16:Initialize \PB{\\{last\_itm}} to a new item with an empty list\X;\6
\&{for} ${}(\|p\MRL{+{\K}}\|j+\T{1};{}$ \|o${},\39\\{isspace}(\\{buf}[\|p]);{}$
${}\|p\PP){}$\1\5
;\2\6
\&{if} ${}(\\{buf}[\|p]\E\.{'|'}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{second}\I\\{max\_cols}){}$\1\5
\\{panic}(\.{"Item\ name\ line\ cont}\)\.{ains\ |\ twice"});\2\6
${}\\{second}\K\\{last\_itm};{}$\6
\&{for} ${}(\|p\PP;{}$ \|o${},\39\\{isspace}(\\{buf}[\|p]);{}$ ${}\|p\PP){}$\1\5
;\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{second}\E\\{max\_cols}){}$\1\5
${}\\{second}\K\\{last\_itm};{}$\2\6
${}\\{oo},\39\\{cl}[\\{last\_itm}].\\{prev}\K\\{last\_itm}-\T{1},\39\\{cl}[%
\\{last\_itm}-\T{1}].\\{next}\K\\{last\_itm};{}$\6
${}\\{oo},\39\\{cl}[\\{second}].\\{prev}\K\\{last\_itm},\39\\{cl}[\\{last%
\_itm}].\\{next}\K\\{second}{}$;\C{ this sequence works properly whether or not
\PB{$\\{second}\K\\{last\_itm}$} }\6
${}\\{oo},\39\\{cl}[\\{root}].\\{prev}\K\\{second}-\T{1},\39\\{cl}[\\{second}-%
\T{1}].\\{next}\K\\{root};{}$\6
${}\\{last\_node}\K\\{last\_itm}{}$;\C{ reserve all the header nodes and the
first spacer }\C{ we have \PB{$\\{nd}[\\{last\_node}].\\{itm}\K\T{0}$} in the
first spacer }\par
\U2.\fi

\M{15}\B\X15:Check for duplicate item name\X${}\E{}$\6
\&{for} ${}(\|k\K\T{1};{}$ \|o${},\39\\{strncmp}(\\{cl}[\|k].\\{name},\39%
\\{cl}[\\{last\_itm}].\\{name},\39\T{8});{}$ ${}\|k\PP){}$\1\5
;\2\6
\&{if} ${}(\|k<\\{last\_itm}){}$\1\5
\\{panic}(\.{"Duplicate\ item\ name}\)\.{"});\2\par
\U14.\fi

\M{16}\B\X16:Initialize \PB{\\{last\_itm}} to a new item with an empty list%
\X${}\E{}$\6
\&{if} ${}(\\{last\_itm}>\\{max\_cols}){}$\1\5
\\{panic}(\.{"Too\ many\ items"});\2\6
${}\\{oo},\39\\{cl}[\\{last\_itm}-\T{1}].\\{next}\K\\{last\_itm},\39\\{cl}[%
\\{last\_itm}].\\{prev}\K\\{last\_itm}-\T{1}{}$;\C{ \PB{$\\{nd}[\\{last\_itm}].%
\\{len}\K\T{0}$} }\6
${}\|o,\39\\{nd}[\\{last\_itm}].\\{up}\K\\{nd}[\\{last\_itm}].\\{down}\K\\{last%
\_itm};{}$\6
${}\\{last\_itm}\PP{}$;\par
\U14.\fi

\M{17}I'm putting the option number into the spacer that follows it, as a
possible debugging aid. But the program doesn't currently use that information.

\Y\B\4\X17:Input the options\X${}\E{}$\6
\&{while} (\T{1})\5
${}\{{}$\1\6
\&{if} ${}(\R\\{fgets}(\\{buf},\39\\{bufsize},\39\\{stdin})){}$\1\5
\&{break};\2\6
\&{if} ${}(\|o,\39\\{buf}[\|p\K\\{strlen}(\\{buf})-\T{1}]\I\.{'\\n'}){}$\1\5
\\{panic}(\.{"Option\ line\ too\ lon}\)\.{g"});\2\6
\&{for} ${}(\|p\K\T{0};{}$ \|o${},\39\\{isspace}(\\{buf}[\|p]);{}$ ${}\|p%
\PP){}$\1\5
;\2\6
\&{if} ${}(\\{buf}[\|p]\E\.{'|'}\V\R\\{buf}[\|p]){}$\1\5
\&{continue};\C{ bypass comment or blank line }\2\6
${}\|i\K\\{last\_node}{}$;\C{ remember the spacer at the left of this option }\6
\&{for} ${}(\\{pp}\K\T{0};{}$ \\{buf}[\|p]; \,)\5
${}\{{}$\1\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\T{8}\W(\|o,\39\R\\{isspace}(\\{buf}[\|p+%
\|j]));{}$ ${}\|j\PP){}$\1\5
${}\|o,\39\\{cl}[\\{last\_itm}].\\{name}[\|j]\K\\{buf}[\|p+\|j];{}$\2\6
\&{if} ${}(\|j\E\T{8}\W\R\\{isspace}(\\{buf}[\|p+\|j])){}$\1\5
\\{panic}(\.{"Item\ name\ too\ long"});\2\6
\&{if} ${}(\|j<\T{8}){}$\1\5
${}\|o,\39\\{cl}[\\{last\_itm}].\\{name}[\|j]\K\.{'\\0'};{}$\2\6
\X18:Create a node for the item named in \PB{\\{buf}[\|p]}\X;\6
\&{for} ${}(\|p\MRL{+{\K}}\|j+\T{1};{}$ \|o${},\39\\{isspace}(\\{buf}[\|p]);{}$
${}\|p\PP){}$\1\5
;\2\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{pp}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vbose}\AND\\{show\_warnings}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Option\ ignored\ (no\ }\)\.{primary\ items):\
"}\|O\.{"s"},\39\\{buf});{}$\2\6
\&{while} ${}(\\{last\_node}>\|i){}$\5
${}\{{}$\1\6
\X20:Remove \PB{\\{last\_node}} from its item list\X;\6
${}\\{last\_node}\MM;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
${}\|o,\39\\{nd}[\|i].\\{down}\K\\{last\_node};{}$\6
${}\\{last\_node}\PP{}$;\C{ create the next spacer }\6
\&{if} ${}(\\{last\_node}\E\\{max\_nodes}){}$\1\5
\\{panic}(\.{"Too\ many\ nodes"});\2\6
${}\\{options}\PP;{}$\6
${}\|o,\39\\{nd}[\\{last\_node}].\\{up}\K\|i+\T{1};{}$\6
${}\|o,\39\\{nd}[\\{last\_node}].\\{itm}\K{-}\\{options};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\M{18}\B\X18:Create a node for the item named in \PB{\\{buf}[\|p]}\X${}\E{}$\6
\&{for} ${}(\|k\K\T{0};{}$ \|o${},\39\\{strncmp}(\\{cl}[\|k].\\{name},\39%
\\{cl}[\\{last\_itm}].\\{name},\39\T{8});{}$ ${}\|k\PP){}$\1\5
;\2\6
\&{if} ${}(\|k\E\\{last\_itm}){}$\1\5
\\{panic}(\.{"Unknown\ item\ name"});\2\6
\&{if} ${}(\|o,\39\\{nd}[\|k].\\{aux}\G\|i){}$\1\5
\\{panic}(\.{"Duplicate\ item\ name}\)\.{\ in\ this\ option"});\2\6
${}\\{last\_node}\PP;{}$\6
\&{if} ${}(\\{last\_node}\E\\{max\_nodes}){}$\1\5
\\{panic}(\.{"Too\ many\ nodes"});\2\6
${}\|o,\39\\{nd}[\\{last\_node}].\\{itm}\K\|k;{}$\6
\&{if} ${}(\|k<\\{second}){}$\1\5
${}\\{pp}\K\T{1};{}$\2\6
${}\|o,\39\|t\K\\{nd}[\|k].\\{len}+\T{1};{}$\6
\X19:Insert node \PB{\\{last\_node}} into the list for item \PB{\|k}\X;\par
\U17.\fi

\M{19}Insertion of a new node is simple, unless we're randomizing.
In the latter case, we want to put the node into a random position
of the list.

We store the position of the new node into \PB{$\\{nd}[\|k].\\{aux}$}, so that
the test for duplicate items above will be correct.

As in other programs developed for TAOCP, I assume that four mems are
consumed when 31 random bits are being generated by any of the {\mc GB\_FLIP}
routines.

\Y\B\4\X19:Insert node \PB{\\{last\_node}} into the list for item \PB{\|k}\X${}%
\E{}$\6
$\|o,\39\\{nd}[\|k].\\{len}\K\|t{}$;\C{ store the new length of the list }\6
${}\\{nd}[\|k].\\{aux}\K\\{last\_node}{}$;\C{ no mem charge for \PB{\\{aux}}
after \PB{\\{len}} }\6
\&{if} ${}(\R\\{randomizing}){}$\5
${}\{{}$\1\6
${}\|o,\39\|r\K\\{nd}[\|k].\\{up}{}$;\C{ the ``bottom'' node of the item list }%
\6
${}\\{ooo},\39\\{nd}[\|r].\\{down}\K\\{nd}[\|k].\\{up}\K\\{last\_node},\39%
\\{nd}[\\{last\_node}].\\{up}\K\|r,\39\\{nd}[\\{last\_node}].\\{down}\K\|k;{}$\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
${}\\{mems}\MRL{+{\K}}\T{4},\39\|t\K\\{gb\_unif\_rand}(\|t){}$;\C{ choose a
random number of nodes to skip past }\6
\&{for} ${}(\|o,\39\|r\K\|k;{}$ \|t; \|o${},\39\|r\K\\{nd}[\|r].\\{down},\39\|t%
\MM){}$\1\5
;\2\6
${}\\{ooo},\39\|q\K\\{nd}[\|r].\\{up},\39\\{nd}[\|q].\\{down}\K\\{nd}[\|r].%
\\{up}\K\\{last\_node};{}$\6
${}\|o,\39\\{nd}[\\{last\_node}].\\{up}\K\|q,\39\\{nd}[\\{last\_node}].\\{down}%
\K\|r;{}$\6
\4${}\}{}$\2\par
\U18.\fi

\M{20}\B\X20:Remove \PB{\\{last\_node}} from its item list\X${}\E{}$\6
$\|o,\39\|k\K\\{nd}[\\{last\_node}].\\{itm};{}$\6
${}\\{oo},\39\\{nd}[\|k].\\{len}\MM,\39\\{nd}[\|k].\\{aux}\K\|i-\T{1};{}$\6
${}\|o,\39\|q\K\\{nd}[\\{last\_node}].\\{up},\39\|r\K\\{nd}[\\{last\_node}].%
\\{down};{}$\6
${}\\{oo},\39\\{nd}[\|q].\\{down}\K\|r,\39\\{nd}[\|r].\\{up}\K\|q{}$;\par
\U17.\fi

\M{21}\B\X21:Report the successful completion of the input phase\X${}\E{}$\6
$\\{fprintf}(\\{stderr},\39\.{"("}\|O\.{"lld\ options,\ "}\|O\.{"d+"}\|O\.{"d\
items,\ "}\|O\.{"d\ entries\ successfu}\)\.{lly\ read)\\n"},\39\\{options},\39%
\\{second}-\T{1},\39\\{last\_itm}-\\{second},\39\\{last\_node}-\\{last%
\_itm}){}$;\par
\U2.\fi

\M{22}The item lengths after input should agree with the item lengths
after this program has finished. I print them (on request), in order to
provide some reassurance that the algorithm isn't badly screwed up.

\Y\B\4\X22:Report the item totals\X${}\E{}$\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Item\ totals:"});{}$\6
\&{for} ${}(\|k\K\T{1};{}$ ${}\|k<\\{last\_itm};{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|k\E\\{second}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"\ |"});{}$\2\6
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{"d"},\39\\{nd}[\|k].\\{len});{}$\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stderr},\39\.{"\\n"});{}$\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{23}The dancing.
Our strategy for generating all exact covers will be to repeatedly
choose always the item that appears to be hardest to cover, namely the
item with shortest list, from all items that still need to be covered.
And we explore all possibilities via depth-first search.

The neat part of this algorithm is the way the lists are maintained.
Depth-first search means last-in-first-out maintenance of data structures;
and it turns out that we need no auxiliary tables to undelete elements from
lists when backing up. The nodes removed from doubly linked lists remember
their former neighbors, because we do no garbage collection.

The basic operation is ``covering an item.'' This means removing it
from the list of items needing to be covered, and ``hiding'' its
options: removing nodes from other lists whenever they belong to an option of
a node in this item's list.

\Y\B\4\X23:Solve the problem\X${}\E{}$\6
$\\{level}\K\T{0};{}$\6
\4\\{forward}:\5
${}\\{nodes}\PP;{}$\6
\&{if} ${}(\\{vbose}\AND\\{show\_profile}){}$\1\5
${}\\{profile}[\\{level}]\PP;{}$\2\6
\&{if} (\\{sanity\_checking})\1\5
\\{sanity}(\,);\2\6
\X25:Do special things if enough \PB{\\{mems}} have accumulated\X;\6
\X30:Set \PB{\\{best\_itm}} to the best item for branching\X;\6
\\{cover}(\\{best\_itm});\6
${}\\{oo},\39\\{cur\_node}\K\\{choice}[\\{level}]\K\\{nd}[\\{best\_itm}].%
\\{down};{}$\6
\4\\{advance}:\5
\&{if} ${}(\\{cur\_node}\E\\{best\_itm}){}$\1\5
\&{goto} \\{backup};\2\6
\&{if} ${}((\\{vbose}\AND\\{show\_choices})\W\\{level}<\\{show\_choices%
\_max}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"L"}\|O\.{"d:"},\39\\{level});{}$\6
${}\\{print\_option}(\\{cur\_node},\39\\{stderr});{}$\6
\4${}\}{}$\2\6
\X28:Cover all other items of \PB{\\{cur\_node}}\X;\6
\&{if} ${}(\|o,\39\\{cl}[\\{root}].\\{next}\E\\{root}){}$\1\5
\X31:Visit a solution and \PB{\&{goto} \\{recover}}\X;\2\6
\&{if} ${}(\PP\\{level}>\\{maxl}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{level}\G\\{max\_level}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Too\ many\ levels!\\n"});{}$\6
${}\\{exit}({-}\T{4});{}$\6
\4${}\}{}$\2\6
${}\\{maxl}\K\\{level};{}$\6
\4${}\}{}$\2\6
\&{goto} \\{forward};\6
\4\\{backup}:\5
\\{uncover}(\\{best\_itm});\6
\&{if} ${}(\\{level}\E\T{0}){}$\1\5
\&{goto} \\{done};\2\6
${}\\{level}\MM;{}$\6
${}\\{oo},\39\\{cur\_node}\K\\{choice}[\\{level}],\39\\{best\_itm}\K\\{nd}[%
\\{cur\_node}].\\{itm};{}$\6
\4\\{recover}:\5
\X29:Uncover all other items of \PB{\\{cur\_node}}\X;\6
${}\\{oo},\39\\{cur\_node}\K\\{choice}[\\{level}]\K\\{nd}[\\{cur\_node}].%
\\{down}{}$;\5
\&{goto} \\{advance};\par
\U2.\fi

\M{24}\B\X3:Global variables\X${}\mathrel+\E{}$\6
\&{int} \\{level};\C{ number of choices in current partial solution }\6
\&{int} \\{choice}[\\{max\_level}];\C{ the node chosen on each level }\6
\&{ullng} \\{profile}[\\{max\_level}];\C{ number of search tree nodes on each
level }\par
\fi

\M{25}\B\X25:Do special things if enough \PB{\\{mems}} have accumulated\X${}%
\E{}$\6
\&{if} ${}(\\{delta}\W(\\{mems}\G\\{thresh})){}$\5
${}\{{}$\1\6
${}\\{thresh}\MRL{+{\K}}\\{delta};{}$\6
\&{if} ${}(\\{vbose}\AND\\{show\_full\_state}){}$\1\5
\\{print\_state}(\,);\2\6
\&{else}\1\5
\\{print\_progress}(\,);\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{mems}\G\\{timeout}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"TIMEOUT!\\n"}){}$;\5
\&{goto} \\{done};\6
\4${}\}{}$\2\par
\U23.\fi

\M{26}When an option is hidden, it leaves all lists except the list of the
item that is being covered. Thus a node is never removed from a list
twice.

Note: I could have saved some mems in this routine, and in similar
routines below, by not updating the \PB{\\{len}} fields of secondary items.
But I chose not to make such an optimization because it might well be
misleading: The insertion of a mem-free new branch `\PB{\&{if} ${}(\\{cc}<%
\\{second})$}'
can be costly since it makes hardware branch prediction less effective.
Furthermore those \PB{\\{len}} fields are in item header nodes, which tend
to remain in cache memory where they're readily accessible.

\Y\B\4\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{cover}(\&{int} \|c)\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \\{cc}${},{}$ \|l${},{}$ \|r${},{}$ \\{rr}${},{}$ %
\\{nn}${},{}$ \\{uu}${},{}$ \\{dd}${},{}$ \|t;\7
${}\|o,\39\|l\K\\{cl}[\|c].\\{prev},\39\|r\K\\{cl}[\|c].\\{next};{}$\6
${}\\{oo},\39\\{cl}[\|l].\\{next}\K\|r,\39\\{cl}[\|r].\\{prev}\K\|l;{}$\6
${}\\{updates}\PP;{}$\6
\&{for} ${}(\|o,\39\\{rr}\K\\{nd}[\|c].\\{down};{}$ ${}\\{rr}\G\\{last%
\_itm};{}$ \|o${},\39\\{rr}\K\\{nd}[\\{rr}].\\{down}){}$\1\6
\&{for} ${}(\\{nn}\K\\{rr}+\T{1};{}$ ${}\\{nn}\I\\{rr};{}$ \,)\5
${}\{{}$\1\6
${}\|o,\39\\{uu}\K\\{nd}[\\{nn}].\\{up},\39\\{dd}\K\\{nd}[\\{nn}].\\{down};{}$\6
${}\|o,\39\\{cc}\K\\{nd}[\\{nn}].\\{itm};{}$\6
\&{if} ${}(\\{cc}\Z\T{0}){}$\5
${}\{{}$\1\6
${}\\{nn}\K\\{uu};{}$\6
\&{continue};\6
\4${}\}{}$\2\6
${}\\{oo},\39\\{nd}[\\{uu}].\\{down}\K\\{dd},\39\\{nd}[\\{dd}].\\{up}\K%
\\{uu};{}$\6
${}\\{updates}\PP;{}$\6
${}\|o,\39\|t\K\\{nd}[\\{cc}].\\{len}-\T{1};{}$\6
${}\|o,\39\\{nd}[\\{cc}].\\{len}\K\|t;{}$\6
${}\\{nn}\PP;{}$\6
\4${}\}{}$\2\2\6
\4${}\}{}$\2\par
\fi

\M{27}I used to think that it was important to uncover an item by
processing its options from bottom to top, since covering was done
from top to bottom. But while writing this
program I realized that, amazingly, no harm is done if the
options are processed again in the same order. So I'll go downward again,
just to prove the point. Whether we go up or down, the pointers
execute an exquisitely choreo\-graphed dance that returns them almost
magically to their former state.

\Y\B\4\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{uncover}(\&{int} \|c)\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \\{cc}${},{}$ \|l${},{}$ \|r${},{}$ \\{rr}${},{}$ %
\\{nn}${},{}$ \\{uu}${},{}$ \\{dd}${},{}$ \|t;\7
\&{for} ${}(\|o,\39\\{rr}\K\\{nd}[\|c].\\{down};{}$ ${}\\{rr}\G\\{last%
\_itm};{}$ \|o${},\39\\{rr}\K\\{nd}[\\{rr}].\\{down}){}$\1\6
\&{for} ${}(\\{nn}\K\\{rr}+\T{1};{}$ ${}\\{nn}\I\\{rr};{}$ \,)\5
${}\{{}$\1\6
${}\|o,\39\\{uu}\K\\{nd}[\\{nn}].\\{up},\39\\{dd}\K\\{nd}[\\{nn}].\\{down};{}$\6
${}\|o,\39\\{cc}\K\\{nd}[\\{nn}].\\{itm};{}$\6
\&{if} ${}(\\{cc}\Z\T{0}){}$\5
${}\{{}$\1\6
${}\\{nn}\K\\{uu};{}$\6
\&{continue};\6
\4${}\}{}$\2\6
${}\\{oo},\39\\{nd}[\\{uu}].\\{down}\K\\{nd}[\\{dd}].\\{up}\K\\{nn};{}$\6
${}\|o,\39\|t\K\\{nd}[\\{cc}].\\{len}+\T{1};{}$\6
${}\|o,\39\\{nd}[\\{cc}].\\{len}\K\|t;{}$\6
${}\\{nn}\PP;{}$\6
\4${}\}{}$\2\2\6
${}\|o,\39\|l\K\\{cl}[\|c].\\{prev},\39\|r\K\\{cl}[\|c].\\{next};{}$\6
${}\\{oo},\39\\{cl}[\|l].\\{next}\K\\{cl}[\|r].\\{prev}\K\|c;{}$\6
\4${}\}{}$\2\par
\fi

\M{28}\B\X28:Cover all other items of \PB{\\{cur\_node}}\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{cur\_node}+\T{1};{}$ ${}\\{pp}\I\\{cur\_node};{}$ \,)\5
${}\{{}$\1\6
${}\|o,\39\\{cc}\K\\{nd}[\\{pp}].\\{itm};{}$\6
\&{if} ${}(\\{cc}\Z\T{0}){}$\1\5
${}\|o,\39\\{pp}\K\\{nd}[\\{pp}].\\{up};{}$\2\6
\&{else}\1\5
${}\\{cover}(\\{cc}),\39\\{pp}\PP;{}$\2\6
\4${}\}{}$\2\par
\U23.\fi

\M{29}When I learned that the covering of individual items can be done safely
in
various orders, I~almost convinced myself that I'd be able
to blithely ignore the ordering---I could apparently
undo the covering of item $a$ then $b$ by uncovering $a$ first.
However, that argument is fallacious: When $a$ is uncovered, it
can resuscitate elements in item~$b$ that would mess up the
uncovering of~$b$. The choreography is delicate indeed.

(Incidentally, the \PB{\\{cover}} and \PB{\\{uncover}} routines both went to
the right.
That was okay. But we must then go left here.)

\Y\B\4\X29:Uncover all other items of \PB{\\{cur\_node}}\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{cur\_node}-\T{1};{}$ ${}\\{pp}\I\\{cur\_node};{}$ \,)\5
${}\{{}$\1\6
${}\|o,\39\\{cc}\K\\{nd}[\\{pp}].\\{itm};{}$\6
\&{if} ${}(\\{cc}\Z\T{0}){}$\1\5
${}\|o,\39\\{pp}\K\\{nd}[\\{pp}].\\{down};{}$\2\6
\&{else}\1\5
${}\\{uncover}(\\{cc}),\39\\{pp}\MM;{}$\2\6
\4${}\}{}$\2\par
\U23.\fi

\M{30}The ``best item'' is considered to be an item that minimizes the
number of remaining choices. If there are several candidates, we
choose the leftmost --- unless we're randomizing, in which case we
select one of them at random.

\Y\B\4\X30:Set \PB{\\{best\_itm}} to the best item for branching\X${}\E{}$\6
$\\{tmems}\K\\{mems},\39\|t\K\\{max\_nodes};{}$\6
\&{if} ${}((\\{vbose}\AND\\{show\_details})\W\\{level}<\\{show\_choices\_max}\W%
\\{level}\G\\{maxl}-\\{show\_choices\_gap}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"Level\ "}\|O\.{"d:"},\39\\{level});{}$\2\6
\&{for} ${}(\|o,\39\|k\K\\{cl}[\\{root}].\\{next};{}$ ${}\|t\W\|k\I\\{root};{}$
\|o${},\39\|k\K\\{cl}[\|k].\\{next}){}$\5
${}\{{}$\1\6
\&{if} ${}((\\{vbose}\AND\\{show\_details})\W\\{level}<\\{show\_choices\_max}\W%
\\{level}\G\\{maxl}-\\{show\_choices\_gap}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{".8s("}\|O\.{"d)"},\39\\{cl}[\|k].%
\\{name},\39\\{nd}[\|k].\\{len});{}$\2\6
\&{if} ${}(\|o,\39\\{nd}[\|k].\\{len}\Z\|t){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{nd}[\|k].\\{len}<\|t){}$\1\5
${}\\{best\_itm}\K\|k,\39\|t\K\\{nd}[\|k].\\{len},\39\|p\K\T{1};{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|p\PP{}$;\C{ this many items achieve the min }\6
\&{if} ${}(\\{randomizing}\W(\\{mems}\MRL{+{\K}}\T{4},\39\R\\{gb\_unif\_rand}(%
\|p))){}$\1\5
${}\\{best\_itm}\K\|k;{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}((\\{vbose}\AND\\{show\_details})\W\\{level}<\\{show\_choices\_max}\W%
\\{level}\G\\{maxl}-\\{show\_choices\_gap}){}$\1\5
${}\\{fprintf}(\\{stderr},\39\.{"\ branching\ on\ "}\|O\.{".8s("}\|O\.{"d)%
\\n"},\39\\{cl}[\\{best\_itm}].\\{name},\39\|t);{}$\2\6
\&{if} ${}(\|t>\\{maxdeg}){}$\1\5
${}\\{maxdeg}\K\|t;{}$\2\6
\&{if} (\\{shape\_file})\5
${}\{{}$\1\6
${}\\{fprintf}(\\{shape\_file},\39\.{""}\|O\.{"d\ "}\|O\.{".8s\\n"},\39\|t,\39%
\\{cl}[\\{best\_itm}].\\{name});{}$\6
\\{fflush}(\\{shape\_file});\6
\4${}\}{}$\2\6
${}\\{cmems}\MRL{+{\K}}\\{mems}-\\{tmems}{}$;\par
\U23.\fi

\M{31}\B\X31:Visit a solution and \PB{\&{goto} \\{recover}}\X${}\E{}$\6
${}\{{}$\1\6
${}\\{nodes}\PP{}$;\C{ a solution is a special node, see 7.2.2--(4) }\6
\&{if} ${}(\\{level}+\T{1}>\\{maxl}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{level}+\T{1}\G\\{max\_level}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Too\ many\ levels!\\n"});{}$\6
${}\\{exit}({-}\T{5});{}$\6
\4${}\}{}$\2\6
${}\\{maxl}\K\\{level}+\T{1};{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\\{vbose}\AND\\{show\_profile}){}$\1\5
${}\\{profile}[\\{level}+\T{1}]\PP;{}$\2\6
\&{if} (\\{shape\_file})\5
${}\{{}$\1\6
${}\\{fprintf}(\\{shape\_file},\39\.{"sol\\n"}){}$;\5
\\{fflush}(\\{shape\_file});\6
\4${}\}{}$\2\6
\X32:Record solution and \PB{\&{goto} \\{recover}}\X;\6
\4${}\}{}$\2\par
\U23.\fi

\M{32}\B\X32:Record solution and \PB{\&{goto} \\{recover}}\X${}\E{}$\6
${}\{{}$\1\6
${}\\{count}\PP;{}$\6
\&{if} ${}(\\{spacing}\W(\\{count}\Xmod\\{spacing}\E\T{0})){}$\5
${}\{{}$\1\6
${}\\{printf}(\.{""}\|O\.{"lld:\\n"},\39\\{count});{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k\Z\\{level};{}$ ${}\|k\PP){}$\1\5
${}\\{print\_option}(\\{choice}[\|k],\39\\{stdout});{}$\2\6
\\{fflush}(\\{stdout});\6
\4${}\}{}$\2\6
\&{if} ${}(\\{count}\G\\{maxcount}){}$\1\5
\&{goto} \\{done};\2\6
\&{goto} \\{recover};\6
\4${}\}{}$\2\par
\U31.\fi

\M{33}\B\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{print\_state}(\&{void})\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \|l;\7
${}\\{fprintf}(\\{stderr},\39\.{"Current\ state\ (leve}\)\.{l\ "}\|O\.{"d):%
\\n"},\39\\{level});{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\\{level};{}$ ${}\|l\PP){}$\5
${}\{{}$\1\6
${}\\{print\_option}(\\{choice}[\|l],\39\\{stderr});{}$\6
\&{if} ${}(\|l\G\\{show\_levels\_max}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\ ...\\n"});{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{"lld\ solutions,\ "}\|O\.{"lld\
mems,\ and\ max\ l}\)\.{evel\ "}\|O\.{"d\ so\ far.\\n"},\39\\{count},\39%
\\{mems},\39\\{maxl});{}$\6
\4${}\}{}$\2\par
\fi

\M{34}During a long run, it's helpful to have some way to measure progress.
The following routine prints a string that indicates roughly where we
are in the search tree. The string consists of character pairs, separated
by blanks, where each character pair represents a branch of the search
tree. When a node has $d$ descendants and we are working on the $k$th,
the two characters respectively represent $k$ and~$d$ in a simple code;
namely, the values 0, 1, \dots, 61 are denoted by
$$\.0,\ \.1,\ \dots,\ \.9,\ \.a,\ \.b,\ \dots,\ \.z,\ \.A,\ \.B,\ \dots,\.Z.$$
All values greater than 61 are shown as `\.*'. Notice that as computation
proceeds, this string will increase lexicographically.

Following that string, a fractional estimate of total progress is computed,
based on the na{\"\i}ve assumption that the search tree has a uniform
branching structure. If the tree consists
of a single node, this estimate is~.5; otherwise, if the first choice
is `$k$ of~$d$', the estimate is $(k-1)/d$ plus $1/d$ times the
recursively evaluated estimate for the $k$th subtree. (This estimate
might obviously be very misleading, in some cases, but at least it
tends to grow monotonically.)

\Y\B\4\X10:Subroutines\X${}\mathrel+\E{}$\6
\1\1\&{void} \\{print\_progress}(\&{void})\2\2\6
${}\{{}$\1\6
\&{register} \&{int} \|l${},{}$ \|k${},{}$ \|d${},{}$ \|c${},{}$ \|p;\6
\&{register} \&{double} \|f${},{}$ \\{fd};\7
${}\\{fprintf}(\\{stderr},\39\.{"\ after\ "}\|O\.{"lld\ mems:\ "}\|O\.{"lld\
sols,"},\39\\{mems},\39\\{count});{}$\6
\&{for} ${}(\|f\K\T{0.0},\39\\{fd}\K\T{1.0},\39\|l\K\T{0};{}$ ${}\|l<%
\\{level};{}$ ${}\|l\PP){}$\5
${}\{{}$\1\6
${}\|c\K\\{nd}[\\{choice}[\|l]].\\{itm},\39\|d\K\\{nd}[\|c].\\{len};{}$\6
\&{for} ${}(\|k\K\T{1},\39\|p\K\\{nd}[\|c].\\{down};{}$ ${}\|p\I\\{choice}[%
\|l];{}$ ${}\|k\PP,\39\|p\K\\{nd}[\|p].\\{down}){}$\1\5
;\2\6
${}\\{fd}\MRL{*{\K}}\|d,\39\|f\MRL{+{\K}}(\|k-\T{1})/\\{fd}{}$;\C{ choice \PB{%
\|l} is \PB{\|k} of \PB{\|d} }\6
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{"c"}\|O\.{"c"},\39\|k<\T{10}\?%
\.{'0'}+\|k:\|k<\T{36}\?\.{'a'}+\|k-\T{10}:\|k<\T{62}\?\.{'A'}+\|k-\T{36}:%
\.{'*'},\39\|d<\T{10}\?\.{'0'}+\|d:\|d<\T{36}\?\.{'a'}+\|d-\T{10}:\|d<\T{62}\?%
\.{'A'}+\|d-\T{36}:\.{'*'});{}$\6
\&{if} ${}(\|l\G\\{show\_levels\_max}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"..."});{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stderr},\39\.{"\ "}\|O\.{".5f\\n"},\39\|f+\T{0.5}/\\{fd});{}$%
\6
\4${}\}{}$\2\par
\fi

\M{35}\B\X35:Print the profile\X${}\E{}$\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Profile:\\n"});{}$\6
\&{for} ${}(\\{level}\K\T{0};{}$ ${}\\{level}\Z\\{maxl};{}$ ${}\\{level}\PP){}$%
\1\5
${}\\{fprintf}(\\{stderr},\39\.{""}\|O\.{"3d:\ "}\|O\.{"lld\\n"},\39\\{level},%
\39\\{profile}[\\{level}]);{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{36}Index.
\fi

\inx
\fin
\con
