@*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; @; @; @; @; } @ @= for (n=k=kk=0;;kk++) { if (!fgets(buf,bufsize,stdin)) break; @; if (kk@; else @; } if (kk= if (!n) { /* this is the first line, which has |n| chars by definition */ for (n=0;buf[n] && buf[n]!='\n';n++) ; /* advance to end of line */ if (n==0) { fprintf(stderr,"the length of the first line (n) is zero!\n"); exit(-1); } if (n>32) { fprintf(stderr,"the length of the first line (%d) exceeds 32!\n", n); exit(-2); } cells=n*n; for (j=0;j= for (j=0;j'0' && buf[j]<='9') pos[k][j]=d=buf[j]-'0'; else if (buf[j]>='a' && buf[j]<='w') pos[k][j]=d=buf[j]-'a'+10; else if (buf[j]=='#') pos[k][j]=-1,cells--,rowcount[k]--,colcount[j]--; else pos[k][j]=0; /* it already is zero, but let's waste time for clarity */ if (pos[k][j]>0) { if (row[k][d-1]) { fprintf(stderr,"digit %c appears in columns %c and %c of row %c!\n", encode(d),encode(row[k][d-1]-1),encode(j),encode(k)); exit(-10); } row[k][d-1]=j+1; if (col[j][d-1]) { fprintf(stderr,"digit %c appears in rows %c and %c of column %c!\n", encode(d),encode(col[j][d-1]-1),encode(k),encode(j)); exit(-11); } col[j][d-1]=k+1; c++; } } @ @= for (j=0;j='0' && buf[j]<='9') x=buf[j]-'0'; else if (buf[j]>='a' && buf[j]<='v') x=buf[j]-'a'+10; else { fprintf(stderr, "line %d of box-definition group %d has the invalid character %c!\n", k,kk/n,buf[j]); exit(-7); } d=pos[k][j]; if (d>0) { if (box[x][d-1]) { fprintf(stderr,"digit %c appears in rows %c and %c of box %c!\n", encode(d),encode(box[x][d-1]-1),encode(k),encode(x)); exit(-12); } box[x][d-1]=k+1; } if (boxcount[x]==0) bc++; if (inbox[k][j]&(1<n) { fprintf(stderr,"box %c contains more than %d cells!\n", encode(x),n); exit(-13); } } @ @= printf("|sudoku"); for (i=0;i0? encode(pos[i][j]): '.'); } fprintf(stdout,"\n"); @ The \.p items precede the \.r items, which precede the \.c items, which precede the \.b items. An item is omitted if there already was a clue for it. An item is secondary if it doesn't need to appear $n$ times. @= for (i=0;i= for (i=0;i