From 2f33ec2c6454614a9e40cc113b5e40df36b7f7ec Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Tue, 9 Aug 2005 16:32:00 +0000 Subject: [PATCH] initial import (automatically generated log message) --- example.txt | 10 + solve.cpp | 638 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 648 insertions(+) create mode 100644 example.txt create mode 100644 solve.cpp diff --git a/example.txt b/example.txt new file mode 100644 index 0000000..22cae02 --- /dev/null +++ b/example.txt @@ -0,0 +1,10 @@ +---4--8-- +95------- +------3-- +-7-15---- +------49- +--1------ +----2--75 +4-86----- +--------- + diff --git a/solve.cpp b/solve.cpp new file mode 100644 index 0000000..59e55c5 --- /dev/null +++ b/solve.cpp @@ -0,0 +1,638 @@ +// Simple Sudoku solver +// Copyright 2005 Steinar H. Gunderson. GPLv2. + +#include +#include +#include +#include +#include +#include +#include +#include + +#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(); + } +} -- 2.39.2