{{ message }}

Instantly share code, notes, and snippets.

# louisswarren/Makefile

Last active Jul 27, 2020
Sudoku solver
 53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79
 .PHONY: test test: seppuku ./seppuku < example.txt seppuku: seppuku.c gcc -std=c99 -o \$@ \$<
 #include #include #include #include #include #define BLANKCELL ((1 << 9) - 1) struct frame { uint16_t soln[9][9]; uint16_t filter[9][9]; }; int is_possible(uint16_t x, int n) { return !!(x & (1 << (n - 1))); } int is_fixed(uint16_t x) { if (!x) return 1; while (!(x & 1)) x >>= 1; return x == 1; } char filtoc(uint16_t x) { int n; for (n = 0; x; ++n) x >>= 1; return n ? '0' + n: ' '; } void pretty_print_frame(struct frame *s) { char bord[] = "-------------------"; char line[] = "| ??? | ??? | ??? |"; int k; printf("%s\n", bord); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { k = j < 3 ? j + 2 : j < 6 ? j + 5 : j + 8; line[k] = filtoc(s->soln[i][j]); } printf("%s\n", line); if (i % 3 == 2) printf("%s\n", bord); } } int remaining(struct frame *s) { int n = 0; for (int i = 0; i < 81; ++i) { if (!s->soln[0][i]) n++; } return n; } uint16_t sum_col_around(uint16_t (*cells)[9][9], int i, int b) { uint16_t sum = 0; for (int j = 0; j < 9; ++j) if (j != b) sum |= (*cells)[i][j]; return sum; } uint16_t sum_row_around(uint16_t (*cells)[9][9], int a, int j) { uint16_t sum = 0; for (int i = 0; i < 9; ++i) if (i != a) sum |= (*cells)[i][j]; return sum; } uint16_t sum_sec_around(uint16_t (*cells)[9][9], int a, int b) { uint16_t sum = 0; for (int i = 3 * (a / 3); i < 3 * (a / 3 + 1); ++i) for (int j = 3 * (b / 3); j < 3 * (b / 3 + 1); ++j) if (i != a || j != b) sum |= (*cells)[i][j]; return sum; } void solve(struct frame *s) { memcpy(&s->filter, &s->soln, sizeof(s->filter)); uint16_t x; int modified = 1; while (modified > 0) { modified = 0; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (s->soln[i][j]) continue; s->filter[i][j] = 0; s->filter[i][j] |= sum_col_around(&s->soln, i, j); s->filter[i][j] |= sum_row_around(&s->soln, i, j); s->filter[i][j] |= sum_sec_around(&s->soln, i, j); s->filter[i][j] = BLANKCELL ^ s->filter[i][j]; if (!s->filter[i][j]) { fprintf(stderr, "Inconsistent: no possible value for cell\n"); } if (is_fixed(s->filter[i][j])) { modified += s->soln[i][j] != s->filter[i][j]; s->soln[i][j] = s->filter[i][j]; } } } if (modified) continue; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (s->soln[i][j]) continue; x = BLANKCELL ^ sum_col_around(&s->filter, i, j); if (x) { // There is a column that can't be solved elsewhere if (!is_fixed(x)) { fprintf(stderr, "Inconsistent: cell must have more than one value\n"); } s->soln[i][j] = x; puts("Helped1"); modified = 1; } else { x = BLANKCELL ^ sum_row_around(&s->filter, i, j); if (x) { if (!is_fixed(x)) { fprintf(stderr, "Inconsistent: cell must have more than one value\n"); } s->soln[i][j] = x; puts("Helped2"); modified = 1; } else { x = BLANKCELL ^ sum_sec_around(&s->filter, i, j); if (x) { if (!is_fixed(x)) { fprintf(stderr, "Inconsistent: cell must have more than one value\n"); } s->soln[i][j] = x; puts("Helped3"); modified = 1; } } } } } } } int main(void) { struct frame *s = calloc(1, sizeof(*s)); int c; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { c = getchar(); if ('1' <= c && c <= '9') { s->soln[i][j] = 1 << (c - '1'); } else if (c != ' ' && c != '.') { fprintf(stderr, "Error on line %d\n", i + 1); exit(1); } } while (getchar() != '\n'); } pretty_print_frame(s); printf("Remaining: %d\n", remaining(s)); printf("\n"); solve(s); pretty_print_frame(s); printf("Remaining: %d\n", remaining(s)); printf("\n"); }
 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179