--- /dev/null
+// Simple Sudoku solver
+// Copyright 2005 Steinar H. Gunderson. GPLv2.
+
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <vector>
+#include <algorithm>
+#include <queue>
+#include <set>
+
+#define WIDTH 9
+#define HEIGHT 9
+#define XGRAN 3
+#define YGRAN 3
+#define NUM (XGRAN*YGRAN)
+
+bool board[WIDTH * HEIGHT][NUM];
+int passes = 0;
+
+char *current_pass;
+int num_current_pass;
+
+void print_board()
+{
+ printf("+");
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ for (unsigned xx = 0; xx < XGRAN; ++xx) {
+ printf("-");
+ }
+ printf("+");
+ }
+ printf("\n");
+
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned yy = 0; yy < YGRAN; ++yy) {
+ printf("|");
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ for (unsigned xx = 0; xx < XGRAN; ++xx) {
+ if (board[y * WIDTH + x][yy * YGRAN + xx]) {
+ printf("%x", yy * YGRAN + xx + 1);
+ } else {
+ printf(" ");
+ }
+ }
+ printf("|");
+ }
+ printf("\n");
+ }
+ printf("+");
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ for (unsigned xx = 0; xx < XGRAN; ++xx) {
+ printf("-");
+ }
+ printf("+");
+ }
+ printf("\n");
+ }
+
+ printf("\n");
+}
+
+bool print_sol()
+{
+ bool complete = true;
+
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ unsigned n = 0, k = 0;
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i]) {
+ ++n;
+ k = i;
+ }
+ }
+
+ if (n == 1) {
+ printf("%x", k + 1);
+ } else {
+ printf("-");
+ complete = false;
+ }
+ }
+ printf("\n");
+ }
+
+ return complete;
+}
+
+// are the opportunities in cell 2 a subset of cell 1? (doesn't have to
+// be a true subset, equality is fine)
+bool cell_is_subset(unsigned x1, unsigned y1, unsigned x2, unsigned y2)
+{
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y1 * WIDTH + x1][i] && board[y2 * WIDTH + x2][i])
+ return false;
+ }
+ return true;
+}
+
+void start_pass(char *name)
+{
+ current_pass = name;
+ num_current_pass = 0;
+}
+
+void impossible(unsigned x, unsigned y, unsigned i)
+{
+ if (board[y * WIDTH + x][i]) {
+ ++num_current_pass;
+ }
+ board[y * WIDTH + x][i] = false;
+}
+
+bool end_pass()
+{
+ if (num_current_pass > 0) {
+ printf("'%s' eliminated %u\n", current_pass, num_current_pass);
+ //print_board();
+ return true;
+ }
+
+ return false;
+}
+
+void block_propagation()
+{
+ // block propagation
+ for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
+ for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
+ for (unsigned y = 0; y < YGRAN; ++y) {
+ for (unsigned x = 0; x < XGRAN; ++x) {
+ unsigned yy = yb*YGRAN + y;
+ unsigned xx = xb*XGRAN + x;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[yy * WIDTH + xx][i])
+ continue;
+
+ // if somebody can't be anything but I, we can't
+ for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
+ for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
+ unsigned yy2 = yb*YGRAN + y2;
+ unsigned xx2 = xb*XGRAN + x2;
+
+ if (yy2 == yy && xx2 == xx)
+ continue;
+
+ for (unsigned j = 0; j < NUM; ++j) {
+ if (i == j && !board[yy2 * WIDTH + xx2][j])
+ goto flexible;
+ if (i != j && board[yy2 * WIDTH + xx2][j])
+ goto flexible;
+ }
+ impossible(xx, yy, i);
+ goto next;
+flexible:
+ 1;
+ }
+ }
+next:
+ 1;
+ }
+ }
+ }
+ }
+ }
+}
+
+void block_propagation2()
+{
+ for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
+ for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
+ for (unsigned y = 0; y < YGRAN; ++y) {
+ for (unsigned x = 0; x < XGRAN; ++x) {
+ unsigned yy = yb*YGRAN + y;
+ unsigned xx = xb*XGRAN + x;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[yy * WIDTH + xx][i])
+ continue;
+
+ // if nobody else can be I, we can't be anything else
+ for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
+ for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
+ unsigned yy2 = yb*YGRAN + y2;
+ unsigned xx2 = xb*XGRAN + x2;
+
+ if (yy2 == yy && xx2 == xx)
+ continue;
+
+ if (board[yy2 * WIDTH + xx2][i])
+ goto no_elim;
+ }
+ }
+
+ for (unsigned j = 0; j < NUM; ++j) {
+ if (i == j || !board[yy * WIDTH + xx][j])
+ continue;
+ impossible(xx, yy, j);
+ }
+no_elim:
+ 1;
+ }
+ }
+ }
+ }
+ }
+}
+
+void block_elimination()
+{
+ for (unsigned y = 0; y < WIDTH; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ // find cells in the same block matching this one exactly
+ unsigned nmatch = 0, ncnt = 0;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i])
+ ++ncnt;
+ }
+
+ if (ncnt == 1)
+ continue; // taken by other logic
+
+ unsigned yb = y/YGRAN;
+ unsigned xb = x/XGRAN;
+
+ for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
+ for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
+ if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2)) {
+ ++nmatch;
+ }
+ }
+ }
+
+ if (nmatch != ncnt)
+ continue;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
+ for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
+ if (!board[(yb*YGRAN + y2) * WIDTH + (xb*XGRAN + x2)][i])
+ continue;
+ if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2))
+ continue;
+
+ impossible(xb*XGRAN + x2, yb*YGRAN + y2, i);
+ }
+ }
+ }
+ }
+ }
+}
+
+void horizontal_propagation()
+{
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ unsigned tyb = y/YGRAN;
+ unsigned txb = x/XGRAN;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
+ if (xb == txb)
+ continue;
+
+ // check if anything not on this line can be I
+ for (unsigned yy = 0; yy < YGRAN; ++yy) {
+ unsigned y2 = tyb * YGRAN + yy;
+ if (y2 == y)
+ continue;
+
+ for (unsigned xx = 0; xx < XGRAN; ++xx) {
+ unsigned x2 = xb * XGRAN + xx;
+ if (board[y2 * WIDTH + x2][i])
+ goto no_go;
+ }
+ }
+
+ impossible(x, y, i);
+no_go:
+ 1;
+ }
+ }
+ }
+ }
+}
+
+void horizontal_propagation2()
+{
+ for (unsigned y = 0; y < WIDTH; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ // if nobody else can be I, we can't be anything else
+ for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
+ if (x2 == x)
+ continue;
+
+ if (board[y * WIDTH + x2][i])
+ goto no_elim_h;
+ }
+
+ for (unsigned j = 0; j < NUM; ++j) {
+ if (i == j || !board[y * WIDTH + x][j])
+ continue;
+ impossible(x, y, j);
+ }
+no_elim_h:
+ 1;
+ }
+ }
+ }
+}
+
+void horizontal_elimination()
+{
+ for (unsigned y = 0; y < WIDTH; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ // find cells on the same row matching this one exactly
+ unsigned nmatch = 0, ncnt = 0;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i])
+ ++ncnt;
+ }
+
+ if (ncnt == 1)
+ continue; // taken by other logic
+
+ for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
+ if (cell_is_subset(x, y, x2, y)) {
+ ++nmatch;
+ }
+ }
+
+ if (nmatch != ncnt)
+ continue;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
+ if (!board[y * WIDTH + x2][i])
+ continue;
+ if (cell_is_subset(x, y, x2, y))
+ continue;
+
+ impossible(x2, y, i);
+ }
+ }
+ }
+ }
+}
+
+void vertical_propagation()
+{
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ unsigned tyb = y/YGRAN;
+ unsigned txb = x/XGRAN;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
+ if (yb == tyb)
+ continue;
+
+ // check if anything not on this column can be I
+ for (unsigned xx = 0; xx < XGRAN; ++xx) {
+ unsigned x2 = txb * XGRAN + xx;
+ if (x2 == x)
+ continue;
+
+ for (unsigned yy = 0; yy < YGRAN; ++yy) {
+ unsigned y2 = yb * YGRAN + yy;
+ if (board[y2 * WIDTH + x2][i])
+ goto no_go_v;
+ }
+ }
+
+ impossible(x, y, i);
+no_go_v:
+ 1;
+ }
+ }
+ }
+ }
+}
+
+void vertical_propagation2()
+{
+ for (unsigned y = 0; y < WIDTH; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ // if nobody else can be I, we can't be anything else
+ for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
+ if (y2 == y)
+ continue;
+
+ if (board[y2 * WIDTH + x][i])
+ goto no_elim_v;
+ }
+
+ for (unsigned j = 0; j < NUM; ++j) {
+ if (i == j || !board[y * WIDTH + x][j])
+ continue;
+ impossible(x, y, j);
+ }
+no_elim_v:
+ 1;
+ }
+ }
+ }
+}
+
+void vertical_elimination()
+{
+ for (unsigned y = 0; y < WIDTH; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ // find cells on the same row matching this one exactly
+ unsigned nmatch = 0, ncnt = 0;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i])
+ ++ncnt;
+ }
+
+ if (ncnt == 1)
+ continue; // taken by other logic
+
+ for (unsigned y2 = 0; y2 < WIDTH; ++y2) {
+ if (cell_is_subset(x, y, x, y2)) {
+ ++nmatch;
+ }
+ }
+
+ if (nmatch != ncnt)
+ continue;
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[y * WIDTH + x][i])
+ continue;
+
+ for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
+ if (!board[y2 * WIDTH + x][i])
+ continue;
+ if (cell_is_subset(x, y, x, y2))
+ continue;
+
+ impossible(x, y2, i);
+ }
+ }
+ }
+ }
+}
+
+bool dead_end()
+{
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ bool ok = false;
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i]) {
+ ok = true;
+ break;
+ }
+ }
+ if (!ok)
+ return true;
+ }
+ }
+
+ return false;
+}
+
+bool solve()
+{
+ //print_board();
+ bool done_anything = false;
+
+ start_pass("Block propagation 1");
+ block_propagation();
+ done_anything |= end_pass();
+
+ start_pass("Block propagation 2");
+ block_propagation2();
+ done_anything |= end_pass();
+
+ start_pass("Block elimination");
+ block_elimination();
+ done_anything |= end_pass();
+
+ start_pass("Horizontal propagation 1");
+ horizontal_propagation();
+ done_anything |= end_pass();
+
+ start_pass("Horizontal propagation 2");
+ horizontal_propagation2();
+ done_anything |= end_pass();
+
+ start_pass("Horizontal elimination");
+ horizontal_elimination();
+ done_anything |= end_pass();
+
+ start_pass("Vertical propagation 1");
+ vertical_propagation();
+ done_anything |= end_pass();
+
+ start_pass("Vertical propagation 2");
+ vertical_propagation2();
+ done_anything |= end_pass();
+
+ start_pass("Vertical elimination");
+ vertical_elimination();
+ done_anything |= end_pass();
+
+ ++passes;
+
+ if (dead_end())
+ return false;
+
+ if (done_anything)
+ return solve(); // always on we march
+
+ // oops, not done anything, and we're not in a self-
+ // contradiction either. need to pick a guess?
+ unsigned best_x = 0, best_y = 0, best_pos = NUM + 1;
+
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ unsigned pos = 0;
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (board[y * WIDTH + x][i])
+ ++pos;
+ }
+
+ if (pos > 1 && pos < best_pos) {
+ best_pos = pos;
+ best_x = x;
+ best_y = y;
+ }
+ }
+ }
+
+ if (best_pos == NUM + 1)
+ return true;
+
+ // uncomment to enable backtracking
+#if 0
+ bool board_copy[WIDTH * HEIGHT][NUM];
+ memcpy(board_copy, board, (WIDTH*HEIGHT)*NUM*sizeof(bool));
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (!board[best_y * WIDTH + best_x][i])
+ continue;
+
+ for (unsigned j = 0; j < NUM; ++j) {
+ if (i == j)
+ continue;
+
+ board[best_y * WIDTH + best_x][j] = false;
+ }
+ if (solve())
+ return true;
+
+ memcpy(board, board_copy, (WIDTH*HEIGHT)*NUM*sizeof(bool));
+ }
+#endif
+
+ return false;
+}
+
+int main()
+{
+ for (unsigned y = 0; y < HEIGHT; ++y)
+ for (unsigned x = 0; x < WIDTH; ++x)
+ for (unsigned i = 0; i < NUM; ++i)
+ board[y * WIDTH + x][i] = true;
+
+ for (unsigned y = 0; y < HEIGHT; ++y) {
+ char buf[256];
+ if (fgets(buf, 256, stdin) == NULL) {
+ fprintf(stderr, "premature eof\n");
+ exit(1);
+ }
+ if (strlen(buf) != WIDTH + 1) {
+ fprintf(stderr, "malformed line %u\n", y);
+ exit(1);
+ }
+ for (unsigned x = 0; x < WIDTH; ++x) {
+ char ch = buf[x];
+ if (ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'G') {
+ unsigned n;
+ if (ch >= '0' && ch <= '9')
+ n = (ch - '0');
+ else
+ n = 10 + (ch - 'A');
+
+ for (unsigned i = 0; i < NUM; ++i) {
+ if (i == n-1)
+ continue;
+ board[y * WIDTH + x][i] = false;
+ }
+ } else if (ch == '-') {
+ } else {
+ fprintf(stderr, "illegal char on line %u\n", y);
+ exit(1);
+ }
+ }
+ }
+
+ bool ok = solve();
+ print_sol();
+
+ if (ok) {
+ printf("\n%u passes\n", passes);
+ } else {
+ printf("\n%u passes (incomplete)\n", passes);
+ print_board();
+ }
+}
projects / sudoku / commitdiff