n) {
fprintf(stderr,"more than %d lines!\n",
n);
@+exit(-8);
}
if (y>n) {
fprintf(stderr,"the entry `%c' exceeds %d!\n",
encode(y),n);
@+exit(-9);
}
fprintf(stderr,
"OK, I've read a %dx%d partial latin square with %d missing entries.\n",
n,n,z);
originaln=n;
@*A bit of theory. Latin squares enjoy lots of symmetry, some of which is
obvious and some of which is less~so. One obvious symmetry is between
rows and columns: The transpose of a latin square is a latin square.
A~less obvious symmetry is between rows and values: If we replace the
permutation in each row by the inverse permutation, we get another latin
square. The same is true for columns, and for partial squares. Thus,
for example, the six partial squares
$$\def\\#1!#2!#3!#4//{\vcenter{\halign{\tt##\cr#1\cr#2\cr#3\cr#4\cr}}}
\\314.!2..1!..1.!..23//\qquad
\\32..!1...!4.12!.1.3//\qquad
\\2.13!41..!3...!.34.//\qquad
\\243.!.1.3!1..4!3...//\qquad
\\.132!2.4.!1..4!..1.//\qquad
\\.21.!1...!23.1!2.4.//$$
are essentially equivalent, obtainable from each other by transposition
and/or inversion.
Many other symmetries are also obvious: We can permute the rows, we can
permute the columns, we can permute the values. But the latter symmetries
aren't especially helpful in the problem we're solving; and it turns out
that transposition isn't important either. We'll see, however, that
row and column inversion are extremely useful.
@ The latin square completion problem is equivalent to another
problem called uniform tripartite triangulation,
whose symmetries are a perfect match. A uniform tripartite graph
is a three-colorable graph in which exactly half of the neighbors of each
vertex are of one color while the other half have the other color.
A triangulation of such a graph is a partition of its edges into triangles.
Every $n\times n$ partial latin square defines a tripartite graph on the
vertices $\{r_1,\ldots,r_n\}$, $\{c_1,\ldots,c_n\}$, and $\{v_1,\ldots,v_n\}$,
if we let
$$\eqalign{&\hbox{$r_i\adj c_j$ $\iff\,$ cell~$(i,j)$ is blank;}\cr
&\hbox{$r_i\adj v_k$ $\iff$ value $k$ doesn't appear in row $i$;}\cr
&\hbox{$c_j\adj v_k$ $\iff$ value $k$ doesn't appear in column $j$.}\cr
}$$
Furthermore, it's not difficult to verify that this tripartite graph
is uniform. One way to see this is to begin with the complete tripartite
graph, which corresponds to a completely blank partial square, and
then to fill in the entries one by one. Whenever we set cell $(i,j)$ to~$k$,
vertices $r_i$ and $c_j$ and $v_k$ each lose two neighbors of
opposite colors.
For example, the tripartite graph for the first partial square above has
the edges
$$\displaylines{\hfill
r_1\adj c_4,\quad
r_2\adj c_2,\quad
r_2\adj c_3,\quad
r_3\adj c_1,\quad
r_3\adj c_2,\quad
r_3\adj c_4,\quad
r_4\adj c_1,\quad
r_4\adj c_2;
\hfill\cr\hfill
r_1\adj v_2,\quad
r_2\adj v_3,\quad
r_2\adj v_4,\quad
r_3\adj v_2,\quad
r_3\adj v_3,\quad
r_3\adj v_4,\quad
r_4\adj v_1,\quad
r_4\adj v_4;
\hfill\cr\hfill
c_1\adj v_1,\quad
c_1\adj v_4,\quad
c_2\adj v_2,\quad
c_2\adj v_3,\quad
c_2\adj v_4,\quad
c_3\adj v_3,\quad
c_4\adj v_2,\quad
c_4\adj v_4;
\hfill\cr}$$
and the other five squares have the same graph but with $\{r,c,v\}$ permuted.
@ Notice that the latin square completion problem is precisely the same as the
task of triangulating
its tripartite graph. And conversely, every uniform tripartite graph
on the vertices $\{r_1,\ldots,r_n\}$, $\{c_1,\ldots,c_n\}$, and
$\{v_1,\ldots,v_n\}$, corresponds to the problem of completing some
$2n\times2n$ latin square. (That latin square has blanks only in its
top left quarter; also, every value $\{n+1,\ldots,2n\}$ occurs in
every row and every column.)
[This theory is due to C.~J. Colbourn, {\sl Discrete Applied Mathematics\/
\bf8} (1984), 25--30, who used it to prove that partial latin square
completion is NP~complete. Notice that the {\it complement\/} of the
tripartite graph that corresponds
to a partial latin square problem is always triangularizable.
Colbourn went up from $n$ to~$2n$, because
a uniform tripartite graph whose complement
isn't triangularizable does not correspond to an $n\times n$ partial
latin square. Perhaps a smaller value than $2n$ would be adequate
in all cases? I don't know. But $n$ itself is too small.]
One consequence of these observations is that two partial latin squares
with the same tripartite graph have exactly the same completion problem.
We don't
need to know any of the values of the nonblank entries, except for
the identities of the missing elements; we don't even have to know~$n$!
In this program,
the problem is defined solely by the zero-or-nonzero state of
the arrays |board|, |R|, and |C|, not by the actual contents
of those three arrays.
@ The triangularization problem, in turn, is equivalent to $3n$
simultaneous bipartite matching problems.
\smallskip\textindent{$\bullet$}The $r_i$ problem:
Match $\{j\mid r_i\adj c_j\}$ with $\{k\mid r_i\adj v_k\}$.
(``Fill row $i$.'')
\smallskip\textindent{$\bullet$}The $c_j$ problem:
Match $\{k\mid c_j\adj v_k\}$ with $\{i\mid c_j\adj r_i\}$.
(``Fill column $j$.'')
\smallskip\textindent{$\bullet$}The $v_k$ problem:
Match $\{i\mid v_k\adj r_i\}$ with $\{j\mid v_k\adj c_j\}$.
(``Fill in the $k$s.'')
\smallskip\noindent
In all three cases, the edges exist precisely when the
exact cover problem defined by {\mc PARTIAL-LATIN-DLX} contains
the option `\.{p$ij$} \.{r$ik$} \.{c$jk$}'. So I shall refer to
``options'' and ``edges'' and ``triples'' interchangeably in the program that
follows. Every such option is, in fact, essentially a triangle,
consisting of three edges---one for the $r_i$ matching,
one for the $c_j$ matching, and one for the $v_k$ matching.
In summary: The problem of completing a partial latin square of size
$n\times n$ is the problem of triangulating a uniform tripartite graph. The
problem of triangulating a uniform tripartite graph with parts of size~$n$
is the problem of doing $3n$ simultaneous bipartite matchings.
This program relies on GAD filtering, which is based on the
rich theory of bipartite matching.
@*Data structures.
Like all interesting problems, this one suggests interesting data structures.
At the lowest level, the input data is represented in small structs called
tetrads, with four fields each: |up|, |down|, |itm|, and |aux|.
Tetrads are modeled after the ``nodes'' in {\mc DLX}; indeed, one good
way to think of this program is to regard it as an exact cover solver
like {\mc DLX}, which has been extended by introducing GAD filtering
to prune unwanted options. The |up| and |down| fields of a tetrad
provide doubly linked lists of options, and the |itm| field refers
to the head of such a list, just as in {\mc DLX}.
The |aux| fields
aren't presently used in any significant way; they're included primarily
so that exactly 16 bytes are allocated, hence |up| and |down| can be fetched
and stored simultaneously. But as long as we have them, we might as well put
a symbolic name into |aux| for use in debugging.
@