@*Intro. Given the specification of a generalized sudoku puzzle in |stdin|,
this program outputs {\mc DLX} data for the problem of finding all solutions.
What is a generalized sudoku puzzle? It is a puzzle whose specification
begins with $n$ lines of $n$ characters each, where $n$ is between 1 and 32.
The characters on these lines are of three kinds:
\smallskip
\item{$\bullet$} A digit from 1 to $n$. (Those digits are \.1, \.2, \dots,
\.9, \.a, \.b, \dots, \.w.) This means that the puzzle will contain this
digit as a clue in this cell.
\item{$\bullet$} The character `\.{\#}'. This means that this cell is
a ``hole'' in the puzzle, not meant to be filled in.
\item{$\bullet$} Any other character. This means that this cell is initially
blank.
\smallskip\noindent
The specification continues with zero or more additional groups of
$n$ lines of $n$ characters. These groups specify ``boxes'' (also called
``regions''). The characters on these lines are of two kinds:
\smallskip
\item{$\bullet$} A digit from 0 to $n-1$. (Those digits are \.0, \.1, \dots,
\.9, \.a, \.b, \dots, \.v.) This means that the cell is part of the box
that has this name.
\item{$\bullet$} The character `\..'. This means nothing. I mean, it
means that nothing about boxes is being specified for this cell in this group.
\smallskip\noindent
Boxes can overlap, but only if they're specified in different groups.
When the input has ended, every box that has been specified should contain
at most $n$ cells.
What is the solution to a generalized sudoku puzzle? It is a way to fill in
all of the initially blank cells, with digits from 1 to~$n$, in such a
way that no digit occurs more than once in any row, column, or box.
Here, for example, is the letter `A' from the Puzzlium ABC,
which was presented by Serhiy and Peter Grabarchuk at the Martin Gardner
Centennial celebration in Berkeley on 26 October 2014:
$$\vcenter{\halign{\tt#\hfil\cr
\#.5..\#\cr
.4..3.\cr
6.\#\#..\cr
.5.2..\cr
.....1\cr
.3\#\#..\cr
.0000.\cr
122203\cr
12..03\cr
122433\cr
144443\cr
11..43\cr
}}$$
It specifies five hexomino boxes. (The reader will enjoy finding its solution.)
The clues are repeated in a comment line at the beginning of the output.
@d bufsize 80
@c
#include
#include
char buf[bufsize];
int pos[32][32]; /* clues and holes */
int row[32][32]; /* does this row contain this clue? */
int col[32][32]; /* does this column contain this clue? */
int box[32][32]; /* does this box contain this clue? */
int rowcount[32],colcount[32],boxcount[32]; /* how many cells in this guy? */
int c; /* how many clues have been given? */
int bc; /* how many boxes have been defined? */
int cells; /* how many cells are left, after holes deducted? */
unsigned int inbox[32][32]; /* which boxes contain this cell? */
main() {
register int d,i,j,k,kk,n,x;
@;
@