/* The MIT License Copyright (c) 2011 by Attractive Chaos Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ // This file implements an improved algorithm of Guenter Stertenbrink's suexco.c // (http://magictour.free.fr/suexco.txt). #include #include #include #include /* For Sudoku, there are 9x9x9=729 possible choices (9 numbers to choose for each cell in a 9x9 grid), and 4x9x9=324 constraints with each constraint representing a set of choices that are mutually conflictive with each other. The 324 constraints are classified into 4 categories: 1. row-column where each cell contains only one number 2. box-number where each number appears only once in one 3x3 box 3. row-number where each number appears only once in one row 4. col-number where each number appears only once in one column Each category consists of 81 constraints. We number these constraints from 0 to 323. In this program, for example, constraint 0 requires that the (0,0) cell contains only one number; constraint 81 requires that number 1 appears only once in the upper-left 3x3 box; constraint 162 requires that number 1 appears only once in row 1; constraint 243 requires that number 1 appears only once in column 1. Noting that a constraint is a subset of choices, we may represent a constraint with a binary vector of 729 elements. Thus we have a 729x324 binary matrix M with M(r,c)=1 indicating the constraint c involves choice r. Solving a Sudoku is reduced to finding a subset of choices such that no choices are present in the same constaint. This is equivalent to finding the minimal subset of choices intersecting all constraints, a minimum hitting set problem or a eqivalence of the exact cover problem. The 729x324 binary matrix is a sparse matrix, with each row containing 4 non-zero elements and each column 9 non-zero elements. In practical implementation, we store the coordinate of non-zero elements instead of the binary matrix itself. We use a binary row vector to indicate the constraints that have not been used and use a column vector to keep the number of times a choice has been forbidden. When we set a choice, we will use up 4 constraints and forbid other choices in the 4 constraints. When we make wrong choices, we will find an unused constraint with all choices forbidden, in which case, we have to backtrack to make new choices. Once we understand what the 729x324 matrix represents, the backtracking algorithm itself is easy. A major difference between the algorithm implemented here and Guenter Stertenbrink's suexco.c lies in how to count the number of the available choices for each constraint. Suexco.c computes the count with a loop, while the algorithm here keeps the count in an array. The latter is a little more complex to implement as we have to keep the counts synchronized all the time, but it is 50-100% faster, depending on the input. */ // the sparse representation of the binary matrix typedef struct { uint16_t r[324][9]; // M(r[c][i], c) is a non-zero element uint16_t c[729][4]; // M(r, c[r][j]) is a non-zero element } sdaux_t; // generate the sparse representation of the binary matrix sdaux_t *sd_genmat() { sdaux_t *a; int i, j, k, r, c, c2, r2; int8_t nr[324]; a = calloc(1, sizeof(sdaux_t)); for (i = r = 0; i < 9; ++i) // generate c[729][4] for (j = 0; j < 9; ++j) for (k = 0; k < 9; ++k) // this "9" means each cell has 9 possible numbers a->c[r][0] = 9 * i + j, // row-column constraint a->c[r][1] = (i/3*3 + j/3) * 9 + k + 81, // box-number constraint a->c[r][2] = 9 * i + k + 162, // row-number constraint a->c[r][3] = 9 * j + k + 243, // col-number constraint ++r; for (c = 0; c < 324; ++c) nr[c] = 0; for (r = 0; r < 729; ++r) // generate r[][] from c[][] for (c2 = 0; c2 < 4; ++c2) k = a->c[r][c2], a->r[k][nr[k]++] = r; return a; } // update the state vectors when we pick up choice r; v=1 for setting choice; v=-1 for reverting static inline int sd_update(const sdaux_t *aux, int8_t sr[729], uint8_t sc[324], int r, int v) { int c2, min = 10, min_c = 0; for (c2 = 0; c2 < 4; ++c2) sc[aux->c[r][c2]] += v<<7; for (c2 = 0; c2 < 4; ++c2) { // update # available choices int r2, rr, cc2, c = aux->c[r][c2]; if (v > 0) { // move forward for (r2 = 0; r2 < 9; ++r2) { if (sr[rr = aux->r[c][r2]]++ != 0) continue; // update the row status for (cc2 = 0; cc2 < 4; ++cc2) { int cc = aux->c[rr][cc2]; if (--sc[cc] < min) // update # allowed choices min = sc[cc], min_c = cc; // register the minimum number } } } else { // revert const uint16_t *p; for (r2 = 0; r2 < 9; ++r2) { if (--sr[rr = aux->r[c][r2]] != 0) continue; // update the row status p = aux->c[rr]; ++sc[p[0]]; ++sc[p[1]]; ++sc[p[2]]; ++sc[p[3]]; // update the count array } } } return min<<16 | min_c; // return the col that has been modified and with the minimal available choices } // solve a Sudoku; _s is the standard dot/number representation int sd_solve(const sdaux_t *aux, const char *_s) { int i, j, r, c, r2, dir, cand, n = 0, min, hints = 0; // dir=1: forward; dir=-1: backtrack int8_t sr[729], cr[81]; // sr[r]: # times the row is forbidden by others; cr[i]: row chosen at step i uint8_t sc[324]; // bit 1-7: # allowed choices; bit 8: the constraint has been used or not int16_t cc[81]; // cc[i]: col chosen at step i char out[82]; for (r = 0; r < 729; ++r) sr[r] = 0; // no row is forbidden for (c = 0; c < 324; ++c) sc[c] = 0<<7|9; // 9 allowed choices; no constraint has been used for (i = 0; i < 81; ++i) { int a = _s[i] >= '1' && _s[i] <= '9'? _s[i] - '1' : -1; // number from -1 to 8 if (a >= 0) sd_update(aux, sr, sc, i * 9 + a, 1); // set the choice if (a >= 0) ++hints; // count the number of hints cr[i] = cc[i] = -1, out[i] = _s[i]; } for (i = 0, dir = 1, cand = 10<<16|0, out[81] = 0;;) { while (i >= 0 && i < 81 - hints) { // maximum 81-hints steps if (dir == 1) { min = cand>>16, cc[i] = cand&0xffff; if (min > 1) { for (c = 0; c < 324; ++c) { if (sc[c] < min) { min = sc[c], cc[i] = c; // choose the top constraint if (min <= 1) break; // this is for acceleration; slower without this line } } } if (min == 0 || min == 10) cr[i--] = dir = -1; // backtrack } c = cc[i]; if (dir == -1 && cr[i] >= 0) sd_update(aux, sr, sc, aux->r[c][cr[i]], -1); // revert the choice for (r2 = cr[i] + 1; r2 < 9; ++r2) // search for the choice to make if (sr[aux->r[c][r2]] == 0) break; // found if the state equals 0 if (r2 < 9) { cand = sd_update(aux, sr, sc, aux->r[c][r2], 1); // set the choice cr[i++] = r2; dir = 1; // moving forward } else cr[i--] = dir = -1; // backtrack } if (i < 0) break; for (j = 0; j < i; ++j) r = aux->r[cc[j]][cr[j]], out[r/9] = r%9 + '1'; // print puts(out); ++n; --i; dir = -1; // backtrack } return n; // return the number of solutions } int main() { sdaux_t *a = sd_genmat(); char buf[1024]; while (fgets(buf, 1024, stdin) != 0) { if (strlen(buf) < 81) continue; sd_solve(a, buf); putchar('\n'); } free(a); return 0; }