1 // Simple Sudoku solver
2 // Copyright 2005 Steinar H. Gunderson. GPLv2.
17 #define NUM (XGRAN*YGRAN)
19 bool board[WIDTH * HEIGHT][NUM];
28 for (unsigned x = 0; x < WIDTH; ++x) {
29 for (unsigned xx = 0; xx < XGRAN; ++xx) {
36 for (unsigned y = 0; y < HEIGHT; ++y) {
37 for (unsigned yy = 0; yy < YGRAN; ++yy) {
39 for (unsigned x = 0; x < WIDTH; ++x) {
40 for (unsigned xx = 0; xx < XGRAN; ++xx) {
41 if (board[y * WIDTH + x][yy * YGRAN + xx]) {
42 printf("%x", yy * YGRAN + xx + 1);
52 for (unsigned x = 0; x < WIDTH; ++x) {
53 for (unsigned xx = 0; xx < XGRAN; ++xx) {
68 for (unsigned y = 0; y < HEIGHT; ++y) {
69 for (unsigned x = 0; x < WIDTH; ++x) {
70 unsigned n = 0, k = 0;
71 for (unsigned i = 0; i < NUM; ++i) {
72 if (board[y * WIDTH + x][i]) {
91 // are the opportunities in cell 2 a subset of cell 1? (doesn't have to
92 // be a true subset, equality is fine)
93 bool cell_is_subset(unsigned x1, unsigned y1, unsigned x2, unsigned y2)
95 for (unsigned i = 0; i < NUM; ++i) {
96 if (!board[y1 * WIDTH + x1][i] && board[y2 * WIDTH + x2][i])
102 void start_pass(char *name)
105 num_current_pass = 0;
108 void impossible(unsigned x, unsigned y, unsigned i)
110 if (board[y * WIDTH + x][i]) {
113 board[y * WIDTH + x][i] = false;
118 if (num_current_pass > 0) {
119 printf("'%s' eliminated %u\n", current_pass, num_current_pass);
127 void block_propagation()
130 for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
131 for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
132 for (unsigned y = 0; y < YGRAN; ++y) {
133 for (unsigned x = 0; x < XGRAN; ++x) {
134 unsigned yy = yb*YGRAN + y;
135 unsigned xx = xb*XGRAN + x;
137 for (unsigned i = 0; i < NUM; ++i) {
138 if (!board[yy * WIDTH + xx][i])
141 // if somebody can't be anything but I, we can't
142 for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
143 for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
144 unsigned yy2 = yb*YGRAN + y2;
145 unsigned xx2 = xb*XGRAN + x2;
147 if (yy2 == yy && xx2 == xx)
150 for (unsigned j = 0; j < NUM; ++j) {
151 if (i == j && !board[yy2 * WIDTH + xx2][j])
153 if (i != j && board[yy2 * WIDTH + xx2][j])
156 impossible(xx, yy, i);
171 void block_propagation2()
173 for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
174 for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
175 for (unsigned y = 0; y < YGRAN; ++y) {
176 for (unsigned x = 0; x < XGRAN; ++x) {
177 unsigned yy = yb*YGRAN + y;
178 unsigned xx = xb*XGRAN + x;
180 for (unsigned i = 0; i < NUM; ++i) {
181 if (!board[yy * WIDTH + xx][i])
184 // if nobody else can be I, we can't be anything else
185 for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
186 for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
187 unsigned yy2 = yb*YGRAN + y2;
188 unsigned xx2 = xb*XGRAN + x2;
190 if (yy2 == yy && xx2 == xx)
193 if (board[yy2 * WIDTH + xx2][i])
198 for (unsigned j = 0; j < NUM; ++j) {
199 if (i == j || !board[yy * WIDTH + xx][j])
201 impossible(xx, yy, j);
212 void block_elimination()
214 for (unsigned y = 0; y < WIDTH; ++y) {
215 for (unsigned x = 0; x < WIDTH; ++x) {
216 // find cells in the same block matching this one exactly
217 unsigned nmatch = 0, ncnt = 0;
219 for (unsigned i = 0; i < NUM; ++i) {
220 if (board[y * WIDTH + x][i])
225 continue; // taken by other logic
227 unsigned yb = y/YGRAN;
228 unsigned xb = x/XGRAN;
230 for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
231 for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
232 if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2)) {
241 for (unsigned i = 0; i < NUM; ++i) {
242 if (!board[y * WIDTH + x][i])
245 for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
246 for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
247 if (!board[(yb*YGRAN + y2) * WIDTH + (xb*XGRAN + x2)][i])
249 if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2))
252 impossible(xb*XGRAN + x2, yb*YGRAN + y2, i);
260 void horizontal_propagation()
262 for (unsigned y = 0; y < HEIGHT; ++y) {
263 for (unsigned x = 0; x < WIDTH; ++x) {
264 unsigned tyb = y/YGRAN;
265 unsigned txb = x/XGRAN;
267 for (unsigned i = 0; i < NUM; ++i) {
268 if (!board[y * WIDTH + x][i])
271 for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
275 // check if anything not on this line can be I
276 for (unsigned yy = 0; yy < YGRAN; ++yy) {
277 unsigned y2 = tyb * YGRAN + yy;
281 for (unsigned xx = 0; xx < XGRAN; ++xx) {
282 unsigned x2 = xb * XGRAN + xx;
283 if (board[y2 * WIDTH + x2][i])
297 void horizontal_propagation2()
299 for (unsigned y = 0; y < WIDTH; ++y) {
300 for (unsigned x = 0; x < WIDTH; ++x) {
301 for (unsigned i = 0; i < NUM; ++i) {
302 if (!board[y * WIDTH + x][i])
305 // if nobody else can be I, we can't be anything else
306 for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
310 if (board[y * WIDTH + x2][i])
314 for (unsigned j = 0; j < NUM; ++j) {
315 if (i == j || !board[y * WIDTH + x][j])
326 void horizontal_elimination()
328 for (unsigned y = 0; y < WIDTH; ++y) {
329 for (unsigned x = 0; x < WIDTH; ++x) {
330 // find cells on the same row matching this one exactly
331 unsigned nmatch = 0, ncnt = 0;
333 for (unsigned i = 0; i < NUM; ++i) {
334 if (board[y * WIDTH + x][i])
339 continue; // taken by other logic
341 for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
342 if (cell_is_subset(x, y, x2, y)) {
350 for (unsigned i = 0; i < NUM; ++i) {
351 if (!board[y * WIDTH + x][i])
354 for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
355 if (!board[y * WIDTH + x2][i])
357 if (cell_is_subset(x, y, x2, y))
360 impossible(x2, y, i);
367 void vertical_propagation()
369 for (unsigned y = 0; y < HEIGHT; ++y) {
370 for (unsigned x = 0; x < WIDTH; ++x) {
371 unsigned tyb = y/YGRAN;
372 unsigned txb = x/XGRAN;
374 for (unsigned i = 0; i < NUM; ++i) {
375 if (!board[y * WIDTH + x][i])
378 for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
382 // check if anything not on this column can be I
383 for (unsigned xx = 0; xx < XGRAN; ++xx) {
384 unsigned x2 = txb * XGRAN + xx;
388 for (unsigned yy = 0; yy < YGRAN; ++yy) {
389 unsigned y2 = yb * YGRAN + yy;
390 if (board[y2 * WIDTH + x2][i])
404 void vertical_propagation2()
406 for (unsigned y = 0; y < WIDTH; ++y) {
407 for (unsigned x = 0; x < WIDTH; ++x) {
408 for (unsigned i = 0; i < NUM; ++i) {
409 if (!board[y * WIDTH + x][i])
412 // if nobody else can be I, we can't be anything else
413 for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
417 if (board[y2 * WIDTH + x][i])
421 for (unsigned j = 0; j < NUM; ++j) {
422 if (i == j || !board[y * WIDTH + x][j])
433 void vertical_elimination()
435 for (unsigned y = 0; y < WIDTH; ++y) {
436 for (unsigned x = 0; x < WIDTH; ++x) {
437 // find cells on the same row matching this one exactly
438 unsigned nmatch = 0, ncnt = 0;
440 for (unsigned i = 0; i < NUM; ++i) {
441 if (board[y * WIDTH + x][i])
446 continue; // taken by other logic
448 for (unsigned y2 = 0; y2 < WIDTH; ++y2) {
449 if (cell_is_subset(x, y, x, y2)) {
457 for (unsigned i = 0; i < NUM; ++i) {
458 if (!board[y * WIDTH + x][i])
461 for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
462 if (!board[y2 * WIDTH + x][i])
464 if (cell_is_subset(x, y, x, y2))
467 impossible(x, y2, i);
476 for (unsigned y = 0; y < HEIGHT; ++y) {
477 for (unsigned x = 0; x < WIDTH; ++x) {
479 for (unsigned i = 0; i < NUM; ++i) {
480 if (board[y * WIDTH + x][i]) {
496 bool done_anything = false;
498 start_pass("Block propagation 1");
500 done_anything |= end_pass();
502 start_pass("Block propagation 2");
503 block_propagation2();
504 done_anything |= end_pass();
506 start_pass("Block elimination");
508 done_anything |= end_pass();
510 start_pass("Horizontal propagation 1");
511 horizontal_propagation();
512 done_anything |= end_pass();
514 start_pass("Horizontal propagation 2");
515 horizontal_propagation2();
516 done_anything |= end_pass();
518 start_pass("Horizontal elimination");
519 horizontal_elimination();
520 done_anything |= end_pass();
522 start_pass("Vertical propagation 1");
523 vertical_propagation();
524 done_anything |= end_pass();
526 start_pass("Vertical propagation 2");
527 vertical_propagation2();
528 done_anything |= end_pass();
530 start_pass("Vertical elimination");
531 vertical_elimination();
532 done_anything |= end_pass();
540 return solve(); // always on we march
542 // oops, not done anything, and we're not in a self-
543 // contradiction either. need to pick a guess?
544 unsigned best_x = 0, best_y = 0, best_pos = NUM + 1;
546 for (unsigned y = 0; y < HEIGHT; ++y) {
547 for (unsigned x = 0; x < WIDTH; ++x) {
549 for (unsigned i = 0; i < NUM; ++i) {
550 if (board[y * WIDTH + x][i])
554 if (pos > 1 && pos < best_pos) {
562 if (best_pos == NUM + 1)
565 // uncomment to enable backtracking
567 bool board_copy[WIDTH * HEIGHT][NUM];
568 memcpy(board_copy, board, (WIDTH*HEIGHT)*NUM*sizeof(bool));
570 for (unsigned i = 0; i < NUM; ++i) {
571 if (!board[best_y * WIDTH + best_x][i])
574 for (unsigned j = 0; j < NUM; ++j) {
578 board[best_y * WIDTH + best_x][j] = false;
583 memcpy(board, board_copy, (WIDTH*HEIGHT)*NUM*sizeof(bool));
592 for (unsigned y = 0; y < HEIGHT; ++y)
593 for (unsigned x = 0; x < WIDTH; ++x)
594 for (unsigned i = 0; i < NUM; ++i)
595 board[y * WIDTH + x][i] = true;
597 for (unsigned y = 0; y < HEIGHT; ++y) {
599 if (fgets(buf, 256, stdin) == NULL) {
600 fprintf(stderr, "premature eof\n");
603 if (strlen(buf) != WIDTH + 1) {
604 fprintf(stderr, "malformed line %u\n", y);
607 for (unsigned x = 0; x < WIDTH; ++x) {
609 if (ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'G') {
611 if (ch >= '0' && ch <= '9')
616 for (unsigned i = 0; i < NUM; ++i) {
619 board[y * WIDTH + x][i] = false;
621 } else if (ch == '-') {
623 fprintf(stderr, "illegal char on line %u\n", y);
633 printf("\n%u passes\n", passes);
635 printf("\n%u passes (incomplete)\n", passes);