git.sesse.net Git - sudoku/blob - solve.cpp

   1 // Simple Sudoku solver
   2 // Copyright 2005 Steinar H. Gunderson. GPLv2.
   3
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include <unistd.h>
   7 #include <stdlib.h>
   8 #include <vector>
   9 #include <algorithm>
  10 #include <queue>
  11 #include <set>
  12
  13 #define WIDTH  9
  14 #define HEIGHT 9
  15 #define XGRAN  3
  16 #define YGRAN  3
  17 #define NUM    (XGRAN*YGRAN)
  18
  19 bool board[WIDTH * HEIGHT][NUM];
  20 int passes = 0;
  21
  22 char *current_pass;
  23 int num_current_pass;
  24
  25 void print_board()
  26 {
  27         printf("+");
  28         for (unsigned x = 0; x < WIDTH; ++x) {
  29                 for (unsigned xx = 0; xx < XGRAN; ++xx) {
  30                         printf("-");
  31                 }
  32                 printf("+");
  33         }
  34         printf("\n");
  35
  36         for (unsigned y = 0; y < HEIGHT; ++y) {
  37                 for (unsigned yy = 0; yy < YGRAN; ++yy) {
  38                         printf("|");
  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);
  43                                         } else {
  44                                                 printf(" ");
  45                                         }
  46                                 }
  47                                 printf("|");
  48                         }
  49                         printf("\n");
  50                 }
  51                 printf("+");
  52                 for (unsigned x = 0; x < WIDTH; ++x) {
  53                         for (unsigned xx = 0; xx < XGRAN; ++xx) {
  54                                 printf("-");
  55                         }
  56                         printf("+");
  57                 }
  58                 printf("\n");
  59         }
  60
  61         printf("\n");
  62 }
  63
  64 bool print_sol()
  65 {
  66         bool complete = true;
  67
  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]) {
  73                                         ++n;
  74                                         k = i;
  75                                 }
  76                         }
  77
  78                         if (n == 1) {
  79                                 printf("%x", k + 1);
  80                         } else {
  81                                 printf("-");
  82                                 complete = false;
  83                         }
  84                 }
  85                 printf("\n");
  86         }
  87
  88         return complete;
  89 }
  90
  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)
  94 {
  95         for (unsigned i = 0; i < NUM; ++i) {
  96                 if (!board[y1 * WIDTH + x1][i] && board[y2 * WIDTH + x2][i])
  97                         return false;
  98         }
  99         return true;
 100 }
 101
 102 void start_pass(char *name)
 103 {
 104         current_pass = name;
 105         num_current_pass = 0;
 106 }
 107
 108 void impossible(unsigned x, unsigned y, unsigned i)
 109 {
 110         if (board[y * WIDTH + x][i]) {
 111                 ++num_current_pass;
 112         }
 113         board[y * WIDTH + x][i] = false;
 114 }
 115
 116 bool end_pass()
 117 {
 118         if (num_current_pass > 0) {
 119                 printf("'%s' eliminated %u\n", current_pass, num_current_pass);
 120                 //print_board();
 121                 return true;
 122         }
 123
 124         return false;
 125 }
 126
 127 void block_propagation()
 128 {
 129         // 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;
 136
 137                                         for (unsigned i = 0; i < NUM; ++i) {
 138                                                 if (!board[yy * WIDTH + xx][i])
 139                                                         continue;
 140
 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;
 146
 147                                                                 if (yy2 == yy && xx2 == xx)
 148                                                                         continue;
 149
 150                                                                 for (unsigned j = 0; j < NUM; ++j) {
 151                                                                         if (i == j && !board[yy2 * WIDTH + xx2][j])
 152                                                                                 goto flexible;
 153                                                                         if (i != j && board[yy2 * WIDTH + xx2][j])
 154                                                                                 goto flexible;
 155                                                                 }
 156                                                                 impossible(xx, yy, i);
 157                                                                 goto next;
 158 flexible:
 159                                                                 1;
 160                                                         }
 161                                                 }
 162 next:
 163                                                 1;
 164                                         }
 165                                 }
 166                         }
 167                 }
 168         }
 169 }
 170
 171 void block_propagation2()
 172 {
 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;
 179
 180                                         for (unsigned i = 0; i < NUM; ++i) {
 181                                                 if (!board[yy * WIDTH + xx][i])
 182                                                         continue;
 183
 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;
 189
 190                                                                 if (yy2 == yy && xx2 == xx)
 191                                                                         continue;
 192
 193                                                                 if (board[yy2 * WIDTH + xx2][i])
 194                                                                         goto no_elim;
 195                                                         }
 196                                                 }
 197
 198                                                 for (unsigned j = 0; j < NUM; ++j) {
 199                                                         if (i == j || !board[yy * WIDTH + xx][j])
 200                                                                 continue;
 201                                                         impossible(xx, yy, j);
 202                                                 }
 203 no_elim:
 204                                                 1;
 205                                         }
 206                                 }
 207                         }
 208                 }
 209         }
 210 }
 211
 212 void block_elimination()
 213 {
 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;
 218
 219                         for (unsigned i = 0; i < NUM; ++i) {
 220                                 if (board[y * WIDTH + x][i])
 221                                         ++ncnt;
 222                         }
 223
 224                         if (ncnt == 1)
 225                                 continue;  // taken by other logic
 226
 227                         unsigned yb = y/YGRAN;
 228                         unsigned xb = x/XGRAN;
 229
 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)) {
 233                                                 ++nmatch;
 234                                         }
 235                                 }
 236                         }
 237
 238                         if (nmatch != ncnt)
 239                                 continue;
 240
 241                         for (unsigned i = 0; i < NUM; ++i) {
 242                                 if (!board[y * WIDTH + x][i])
 243                                         continue;
 244
 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])
 248                                                         continue;
 249                                                 if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2))
 250                                                         continue;
 251
 252                                                 impossible(xb*XGRAN + x2, yb*YGRAN + y2, i);
 253                                         }
 254                                 }
 255                         }
 256                 }
 257         }
 258 }
 259
 260 void horizontal_propagation()
 261 {
 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;
 266
 267                         for (unsigned i = 0; i < NUM; ++i) {
 268                                 if (!board[y * WIDTH + x][i])
 269                                         continue;
 270
 271                                 for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
 272                                         if (xb == txb)
 273                                                 continue;
 274
 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;
 278                                                 if (y2 == y)
 279                                                         continue;
 280
 281                                                 for (unsigned xx = 0; xx < XGRAN; ++xx) {
 282                                                         unsigned x2 = xb * XGRAN + xx;
 283                                                         if (board[y2 * WIDTH + x2][i])
 284                                                                 goto no_go;
 285                                                 }
 286                                         }
 287
 288                                         impossible(x, y, i);
 289 no_go:
 290                                         1;
 291                                 }
 292                         }
 293                 }
 294         }
 295 }
 296
 297 void horizontal_propagation2()
 298 {
 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])
 303                                         continue;
 304
 305                                 // if nobody else can be I, we can't be anything else
 306                                 for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
 307                                         if (x2 == x)
 308                                                 continue;
 309
 310                                         if (board[y * WIDTH + x2][i])
 311                                                 goto no_elim_h;
 312                                 }
 313
 314                                 for (unsigned j = 0; j < NUM; ++j) {
 315                                         if (i == j || !board[y * WIDTH + x][j])
 316                                                 continue;
 317                                         impossible(x, y, j);
 318                                 }
 319 no_elim_h:
 320                                 1;
 321                         }
 322                 }
 323         }
 324 }
 325
 326 void horizontal_elimination()
 327 {
 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;
 332
 333                         for (unsigned i = 0; i < NUM; ++i) {
 334                                 if (board[y * WIDTH + x][i])
 335                                         ++ncnt;
 336                         }
 337
 338                         if (ncnt == 1)
 339                                 continue;  // taken by other logic
 340
 341                         for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
 342                                 if (cell_is_subset(x, y, x2, y)) {
 343                                         ++nmatch;
 344                                 }
 345                         }
 346
 347                         if (nmatch != ncnt)
 348                                 continue;
 349
 350                         for (unsigned i = 0; i < NUM; ++i) {
 351                                 if (!board[y * WIDTH + x][i])
 352                                         continue;
 353
 354                                 for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
 355                                         if (!board[y * WIDTH + x2][i])
 356                                                 continue;
 357                                         if (cell_is_subset(x, y, x2, y))
 358                                                 continue;
 359
 360                                         impossible(x2, y, i);
 361                                 }
 362                         }
 363                 }
 364         }
 365 }
 366
 367 void vertical_propagation()
 368 {
 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;
 373
 374                         for (unsigned i = 0; i < NUM; ++i) {
 375                                 if (!board[y * WIDTH + x][i])
 376                                         continue;
 377
 378                                 for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
 379                                         if (yb == tyb)
 380                                                 continue;
 381
 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;
 385                                                 if (x2 == x)
 386                                                         continue;
 387
 388                                                 for (unsigned yy = 0; yy < YGRAN; ++yy) {
 389                                                         unsigned y2 = yb * YGRAN + yy;
 390                                                         if (board[y2 * WIDTH + x2][i])
 391                                                                 goto no_go_v;
 392                                                 }
 393                                         }
 394
 395                                         impossible(x, y, i);
 396 no_go_v:
 397                                         1;
 398                                 }
 399                         }
 400                 }
 401         }
 402 }
 403
 404 void vertical_propagation2()
 405 {
 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])
 410                                         continue;
 411
 412                                 // if nobody else can be I, we can't be anything else
 413                                 for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
 414                                         if (y2 == y)
 415                                                 continue;
 416
 417                                         if (board[y2 * WIDTH + x][i])
 418                                                 goto no_elim_v;
 419                                 }
 420
 421                                 for (unsigned j = 0; j < NUM; ++j) {
 422                                         if (i == j || !board[y * WIDTH + x][j])
 423                                                 continue;
 424                                         impossible(x, y, j);
 425                                 }
 426 no_elim_v:
 427                                 1;
 428                         }
 429                 }
 430         }
 431 }
 432
 433 void vertical_elimination()
 434 {
 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;
 439
 440                         for (unsigned i = 0; i < NUM; ++i) {
 441                                 if (board[y * WIDTH + x][i])
 442                                         ++ncnt;
 443                         }
 444
 445                         if (ncnt == 1)
 446                                 continue;  // taken by other logic
 447
 448                         for (unsigned y2 = 0; y2 < WIDTH; ++y2) {
 449                                 if (cell_is_subset(x, y, x, y2)) {
 450                                         ++nmatch;
 451                                 }
 452                         }
 453
 454                         if (nmatch != ncnt)
 455                                 continue;
 456
 457                         for (unsigned i = 0; i < NUM; ++i) {
 458                                 if (!board[y * WIDTH + x][i])
 459                                         continue;
 460
 461                                 for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
 462                                         if (!board[y2 * WIDTH + x][i])
 463                                                 continue;
 464                                         if (cell_is_subset(x, y, x, y2))
 465                                                 continue;
 466
 467                                         impossible(x, y2, i);
 468                                 }
 469                         }
 470                 }
 471         }
 472 }
 473
 474 bool dead_end()
 475 {
 476         for (unsigned y = 0; y < HEIGHT; ++y) {
 477                 for (unsigned x = 0; x < WIDTH; ++x) {
 478                         bool ok = false;
 479                         for (unsigned i = 0; i < NUM; ++i) {
 480                                 if (board[y * WIDTH + x][i]) {
 481                                         ok = true;
 482                                         break;
 483                                 }
 484                         }
 485                         if (!ok)
 486                                 return true;
 487                 }
 488         }
 489
 490         return false;
 491 }
 492
 493 bool solve()
 494 {
 495         //print_board();
 496         bool done_anything = false;
 497
 498         start_pass("Block propagation 1");
 499         block_propagation();
 500         done_anything |= end_pass();
 501
 502         start_pass("Block propagation 2");
 503         block_propagation2();
 504         done_anything |= end_pass();
 505
 506         start_pass("Block elimination");
 507         block_elimination();
 508         done_anything |= end_pass();
 509
 510         start_pass("Horizontal propagation 1");
 511         horizontal_propagation();
 512         done_anything |= end_pass();
 513
 514         start_pass("Horizontal propagation 2");
 515         horizontal_propagation2();
 516         done_anything |= end_pass();
 517
 518         start_pass("Horizontal elimination");
 519         horizontal_elimination();
 520         done_anything |= end_pass();
 521
 522         start_pass("Vertical propagation 1");
 523         vertical_propagation();
 524         done_anything |= end_pass();
 525
 526         start_pass("Vertical propagation 2");
 527         vertical_propagation2();
 528         done_anything |= end_pass();
 529
 530         start_pass("Vertical elimination");
 531         vertical_elimination();
 532         done_anything |= end_pass();
 533
 534         ++passes;
 535
 536         if (dead_end())
 537                 return false;
 538
 539         if (done_anything)
 540                 return solve();   // always on we march
 541
 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;
 545
 546         for (unsigned y = 0; y < HEIGHT; ++y) {
 547                 for (unsigned x = 0; x < WIDTH; ++x) {
 548                         unsigned pos = 0;
 549                         for (unsigned i = 0; i < NUM; ++i) {
 550                                 if (board[y * WIDTH + x][i])
 551                                         ++pos;
 552                         }
 553
 554                         if (pos > 1 && pos < best_pos) {
 555                                 best_pos = pos;
 556                                 best_x = x;
 557                                 best_y = y;
 558                         }
 559                 }
 560         }
 561
 562         if (best_pos == NUM + 1)
 563                 return true;
 564
 565         // uncomment to enable backtracking
 566 #if 0
 567         bool board_copy[WIDTH * HEIGHT][NUM];
 568         memcpy(board_copy, board, (WIDTH*HEIGHT)*NUM*sizeof(bool));
 569
 570         for (unsigned i = 0; i < NUM; ++i) {
 571                 if (!board[best_y * WIDTH + best_x][i])
 572                         continue;
 573
 574                 for (unsigned j = 0; j < NUM; ++j) {
 575                         if (i == j)
 576                                 continue;
 577
 578                         board[best_y * WIDTH + best_x][j] = false;
 579                 }
 580                 if (solve())
 581                         return true;
 582
 583                 memcpy(board, board_copy, (WIDTH*HEIGHT)*NUM*sizeof(bool));
 584         }
 585 #endif
 586
 587         return false;
 588 }
 589
 590 int main()
 591 {
 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;
 596
 597         for (unsigned y = 0; y < HEIGHT; ++y) {
 598                 char buf[256];
 599                 if (fgets(buf, 256, stdin) == NULL) {
 600                         fprintf(stderr, "premature eof\n");
 601                         exit(1);
 602                 }
 603                 if (strlen(buf) != WIDTH + 1) {
 604                         fprintf(stderr, "malformed line %u\n", y);
 605                         exit(1);
 606                 }
 607                 for (unsigned x = 0; x < WIDTH; ++x) {
 608                         char ch = buf[x];
 609                         if (ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'G') {
 610                                 unsigned n;
 611                                 if (ch >= '0' && ch <= '9')
 612                                         n = (ch - '0');
 613                                 else
 614                                         n = 10 + (ch - 'A');
 615
 616                                 for (unsigned i = 0; i < NUM; ++i) {
 617                                         if (i == n-1)
 618                                                 continue;
 619                                         board[y * WIDTH + x][i] = false;
 620                                 }
 621                         } else if (ch == '-') {
 622                         } else {
 623                                 fprintf(stderr, "illegal char on line %u\n", y);
 624                                 exit(1);
 625                         }
 626                 }
 627         }
 628
 629         bool ok = solve();
 630         print_sol();
 631
 632         if (ok) {
 633                 printf("\n%u passes\n", passes);
 634         } else {
 635                 printf("\n%u passes (incomplete)\n", passes);
 636                 print_board();
 637         }
 638 }