\datethis @*Intro. Mike Spivey announced a programming contest in February 2005, asking for a program that solves ``sudoku'' puzzles (which evidently appear daily in British newspapers). This program takes a sudoku specification in standard input and creates --- on standard output --- a file that can be piped into {\mc DANCE} in order to deduce all solutions. Brief explanation: Each possible placement of a digit corresponds to a row, column, and box where that digit does not yet appear. We want an exact cover of those rows, columns, and boxes. Apology: I wrote this in a big hurry. But I couldn't resist the task, because it is such a nice application of exact covering. @c #include char buf[11]; int row[9][10], col[9][10], box[9][10]; /* things to cover */ int board[9][9]; /* positions already filled */ main() { register int j,k,d,x; for (k=0;k<9;k++) @; @; for (j=0;j<9;j++) for (k=0;k<9;k++) if (!board[k][j]) @; } @ In a production system I would of course try to give more informative error messages about malformed input data. Here I simply quit, if the rules haven't been followed. @d panic(m) {@+fprintf(stderr,"%s!\n%s",m,buf);@+exit(-1);@+} @= { fgets(buf,11,stdin); if (buf[9]!='\n') panic("Input line should have 9 characters exactly!\n"); for (j=0;j<9;j++) if (buf[j]!='.') { if (buf[j]<'1' || buf[j]>'9') panic("Illegal character in input!\n"); d=buf[j]-'0'; if (row[k][d]) panic("Two identical digits in a row!\n"); row[k][d]=1; if (col[j][d]) panic("Two identical digits in a column!\n"); col[j][d]=1; x=((int)(k/3))*3+((int)(j/3)); if (box[x][d]) panic("Two identical digits in a box!\n"); box[x][d]=1; board[k][j]=1; } } @ First we print out all the positions, rows, columns, and boxes that need to be covered. @= for (k=0;k<9;k++) for (j=0;j<9;j++) if (!board[k][j]) printf(" p%d%d",k,j); for (k=0;k<9;k++) for (d=1;d<=9;d++) { if (!row[k][d]) printf(" r%d%d",k,d); if (!col[k][d]) printf(" c%d%d",k,d); if (!box[k][d]) printf(" b%d%d",k,d); } printf("\n"); @ Then we print out all the possible placements. @= { x=((int)(k/3))*3+((int)(j/3)); for (d=1;d<=9;d++) if (!row[k][d] && !col[j][d] && !box[x][d]) printf("p%d%d r%d%d c%d%d b%d%d\n",k,j,k,d,j,d,x,d); } @*Index.