git.itanic.dy.fi Git - sudoku/blob - sudoku.cpp

   1 #include <iostream>
   2 #include <string>
   3
   4 #include "sudoku.h"
   5 #include "debug.h"
   6 #include "random.h"
   7
   8 #define EMPTY ' '
   9
  10 int verbose = 1;
  11
  12 sudoku::sudoku()
  13 {
  14         int x,y;
  15
  16         for (y = 0; y < 9; y++)
  17                 for (x = 0; x < 9; x++)
  18                         table[x][y] = EMPTY;
  19
  20         recursion_depth = 0;
  21         guesses = 0;
  22 }
  23
  24 sudoku::~sudoku()
  25 {
  26 }
  27
  28 static int check_validity(const int col, const int row)
  29 {
  30         if (col < 0 || col >= 9) {
  31                 DPRINT << "Invalid column: " << col << std::endl;
  32                 return 0;
  33         }
  34
  35         if (row < 0 || row >= 9) {
  36                 DPRINT << "Invalid row: " << row << std::endl;
  37                 return 0;
  38         }
  39         return 1;
  40 }
  41
  42 char sudoku::get(const int col, const int row)
  43 {
  44         if (!check_validity(row, col)) {
  45                 DPRINT << "over here\n";
  46                 return 0;
  47         }
  48
  49         return table[col][row];
  50 }
  51
  52 int sudoku::set(const int col, const int row, const char val)
  53 {
  54         std::string str;
  55
  56         if (!check_validity(col, row)) {
  57                 DPRINT << "over here\n";
  58                 return -1;
  59         }
  60
  61         if (table[col][row] != EMPTY) {
  62                 DPRINT << "Assigning value to a non-empty slot\n";
  63                 return -1;
  64         }
  65
  66         str = get_col_contents(col);
  67         if (str.find(val, 0) != std::string::npos) {
  68                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  69                        << val << std::endl;
  70                 return -1;
  71         }
  72
  73         str = get_row_contents(row);
  74         if (str.find(val, 0) != std::string::npos) {
  75                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  76                        << val << std::endl;
  77                 return -1;
  78         }
  79
  80         str = get_block_contents(col, row);
  81         if (str.find(val, 0) != std::string::npos) {
  82                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  83                        << val << std::endl;
  84                 return -1;
  85         }
  86
  87         table[col][row] = val;
  88
  89         return 0;
  90 }
  91
  92 int sudoku::str_to_row(const int row, const std::string &str)
  93 {
  94         unsigned int i, col = 0;
  95         char chr;
  96
  97         if (row < 0 || row >= 9) {
  98                 DPRINT << "Illegal row " << row << std::endl;
  99                 return -1;
 100         }
 101
 102         for (i = 0; i < str.length(); i++) {
 103                 chr = str.at(i);
 104
 105                 if ((chr == '?') ||
 106                     (chr == '_') ||
 107                     (chr == '.')){
 108                         col++;
 109                         continue;
 110                 }
 111
 112                 /* Ignore non-numbers */
 113                 if (chr < '1' || chr > '9')
 114                         continue;
 115
 116                 set(col++, row, chr);
 117                 if (col >= 9)
 118                         break;
 119         }
 120         return 0;
 121 }
 122
 123 void sudoku::print(void)
 124 {
 125         int x, y;
 126
 127         printf("+-------+------+--------+\n");
 128         for (y = 0; y < 9; y++) {
 129                 printf("| ");
 130                 for (x = 0; x < 9; x++) {
 131                         printf("%c ", table[x][y]);
 132                         if (!((x  + 1)% 3))
 133                                 printf("| ");
 134                 }
 135                 printf("\n");
 136                 if (!((y + 1) % 3))
 137                         printf("+-------+-------+-------+\n");
 138         }
 139 }
 140
 141 void sudoku::print_compact(void)
 142 {
 143         int x, y, i = 0;
 144         char str[82];
 145         str[81] = 0;
 146
 147         for (y = 0; y < 9; y++)
 148                 for (x = 0; x < 9; x++, i++)
 149                         str[i] = table[x][y] != EMPTY ? table[x][y] : '.';
 150
 151         printf("%s\n", str);
 152 }
 153
 154 std::string sudoku::get_row_contents(int row)
 155 {
 156         std::string s;
 157         int col;
 158
 159         for (col = 0; col < 9; col++) {
 160                 if (table[col][row] != EMPTY)
 161                         s += table[col][row];
 162         }
 163
 164         return s;
 165 }
 166
 167 std::string sudoku::get_col_contents(int col)
 168 {
 169         std::string s;
 170         int row;
 171
 172         for (row = 0; row < 9; row++) {
 173                 if (table[col][row] != EMPTY)
 174                         s += table[col][row];
 175         }
 176
 177         return s;
 178 }
 179
 180 std::string sudoku::get_block_contents(int col, int row)
 181 {
 182         std::string s;
 183         int x, y;
 184         char c;
 185
 186         if (col < 0 || col >= 9)
 187                 DPRINT "Aiee " << col << std::endl;
 188         if (row < 0 || row >= 9)
 189                 DPRINT "Aiee " << row << std::endl;
 190
 191         col = (col /= 3) * 3;
 192         row = (row /= 3) * 3;
 193
 194         for (y = 0; y < 3; y++)
 195                 for (x = 0; x < 3; x++) {
 196                         c = get(x + col, y + row);
 197                         if (c != EMPTY)
 198                                 s += c;
 199                 }
 200
 201         return s;
 202 }
 203
 204 static std::string exclude_common(std::string s1, std::string s2)
 205 {
 206         std::string::iterator a, b;
 207
 208 restart:
 209         for (a = s1.begin(); a != s1.end(); a++) {
 210                 for (b = s2.begin(); b != s2.end(); b++) {
 211                         if (*a == *b) {
 212                                 a = s1.erase(a);
 213                                 b = s2.erase(b);
 214                                 goto restart;
 215                         }
 216                 }
 217         }
 218         return s1;
 219 }
 220
 221 std::string sudoku::get_legal_numbers(int col, int row)
 222 {
 223         char val;
 224         std::string a, b, c, ret;
 225
 226         if (!check_validity(col, row)) {
 227                 DPRINT << "over here\n";
 228                 return NULL;
 229         }
 230
 231         val = get(col, row);
 232         if (val != EMPTY) {
 233                 return "0";
 234         }
 235
 236 //      std::cout << "[" << col << "." << row << "] ";
 237
 238         a = get_col_contents(col);
 239 //      std::cout << " col " << a;
 240
 241         b = get_row_contents(row);
 242 //      std::cout << " row " << b;
 243
 244         c = get_block_contents(col, row);
 245 //      std::cout << " block " << c;
 246
 247         ret = exclude_common("123456789", a);
 248         ret = exclude_common(ret, b);
 249         ret = exclude_common(ret, c);
 250
 251 //      std::cout << " legal " << ret << std::endl;
 252         return ret;
 253 }
 254
 255 int sudoku::fill_missing()
 256 {
 257         int x, y, solved = 0;
 258         std::string num;
 259
 260         for (y = 0; y < 9; y++)
 261                 for (x = 0; x < 9; x++) {
 262                                 num = get_legal_numbers(x, y);
 263                                 if ((num != "0") && (num.length() == 1)) {
 264                                         set(x, y, num[0]);
 265                                         solved++;
 266                         }
 267                 }
 268         if (verbose) {
 269                 //std::cout << "Solved " << solved << " numbers\n";
 270         }
 271
 272         return solved;
 273 }
 274
 275 int sudoku::get_best_guess(int &col, int &row)
 276 {
 277         int x, y;
 278         int min = 0, filled = 0, illegals = 0;
 279         std::string numbers;
 280
 281         /*
 282          * Initialize row and col with illegal values to spot possible
 283          * misuse
 284          */
 285         col = -1;
 286         row = -1;
 287
 288         for (y = 0; (y < 9) && !illegals; y++)
 289                 for (x = 0; x < 9; x++) {
 290                         numbers = get_legal_numbers(x, y);
 291
 292                         if (numbers == "0") {
 293                                 filled++;
 294                                 continue;
 295                         }
 296
 297                         if (numbers.length() == 0) {
 298                                 illegals++;
 299                                 break;
 300                         }
 301
 302                         if (!min) {
 303                                 min = numbers.length();
 304                                 col = x;
 305                                 row = y;
 306                                 continue;
 307                         }
 308
 309                         if ((int)numbers.length() < min) {
 310                                 min = numbers.length();
 311                                 col = x;
 312                                 row = y;
 313                                 if (min == 1)
 314                                         return min;
 315                         }
 316 //                      std::cout <<  x << "." << y << ": " << " min "
 317 //                                << numbers << col << "." << row << std::endl;
 318                 }
 319
 320         if ((!min && !filled) || illegals) {
 321 //              DPRINT << "Is this sudoku has no solutions?\n";
 322                 return -1;
 323         }
 324
 325         if (!min && (filled == 99)) {
 326                 DPRINT << "This sudoku is solved\n";
 327                 return 0;
 328         }
 329
 330         return min;
 331 }
 332
 333 std::vector<sudoku> sudoku::solve_all()
 334 {
 335         int x, y, i, j, ret;
 336         std::string str;
 337         std::vector<sudoku> sudokus;
 338
 339         // Fill in as much as possible
 340         do {
 341                 if (verbose) {
 342                         std::cout << std::endl;
 343                         print();
 344                 }
 345         } while (fill_missing() != 0);
 346
 347         ret = get_best_guess(x, y);
 348
 349         // Did we solve it yet?
 350         switch (ret) {
 351         case -1:
 352                 // Unsolvable
 353                 if (verbose) {
 354                         std::cout << "This is unsolvable, recursion: "
 355                                   << recursion_depth << std::endl;
 356                 }
 357                 return sudokus;
 358         case 0:
 359                 // Solved
 360                 if (verbose) {
 361                         std::cout << "Solution found , recursion: "
 362                                   << recursion_depth << std::endl;
 363                 }
 364                 sudokus.push_back(*this);
 365                 if (verbose)
 366                         print();
 367                 return sudokus;
 368         }
 369
 370         if (verbose) {
 371                 std::cout << "Not solved yet, guessing at depth "
 372                           << recursion_depth << std::endl;
 373         }
 374
 375         // Try guessim something
 376         str = get_legal_numbers(x, y);
 377         for (i = 0; i < (int)str.length(); i++) {
 378                 std::vector<sudoku> results;
 379
 380                 sudoku guess = *this;
 381                 guesses++;
 382
 383                 if (verbose) {
 384                         std::cout << "Guessing number " << str[i] << " to "
 385                                   << x << "." << y << std::endl;
 386                 }
 387
 388                 guess.set(x, y, str[i]);
 389                 guess.recursion_depth = recursion_depth + 1;
 390                 guess.guesses = 0;
 391
 392                 results = guess.solve_all();
 393                 guesses += guess.guesses;
 394
 395                 //Did it solve?
 396                 if (!results.empty()) {
 397 /*                      printf("Got %d solutions, guessed %d: %s\n",
 398                                (int)results.size(), (int)str.size(),
 399                                str.c_str());*/
 400
 401                         for(j = 0;j < (int)results.size(); j++) {
 402                                 sudokus.push_back(results.at(j));
 403                                 guesses += results.at(j).guesses;
 404                         }
 405                 }
 406         }
 407
 408         if (verbose)
 409                 std::cout << "Guesses: " << guesses << std::endl;
 410
 411         // Return what was solved
 412         return sudokus;
 413 }
 414
 415 sudoku sudoku::fill_with_random(int &solvable)
 416 {
 417         int x, y, i, ret;
 418         std::string str;
 419         sudoku empty;
 420
 421         // Fill in as much as possible
 422         do {
 423                 if (verbose) {
 424                         //std::cout << std::endl;
 425                         //print();
 426                 }
 427         } while (fill_missing() != 0);
 428
 429         ret = get_best_guess(x, y);
 430
 431         // Did we fill it yet?
 432         switch (ret) {
 433         case -1:
 434                 // Unsolvable
 435                 solvable = 0;
 436                 if (verbose) {
 437                         //std::cout << "This is unsolvable, recursion: "
 438                         //  << recursion_depth << std::endl;
 439                 }
 440                 return empty;
 441         case 0:
 442                 // Solved
 443                 solvable = 1;
 444                 if (verbose) {
 445                         //std::cout << "Solution found , recursion: "
 446                         //  << recursion_depth << std::endl;
 447                 }
 448                 return *this;
 449         }
 450
 451         if (verbose) {
 452                 //std::cout << "Not solved yet, guessing at depth "
 453                 //  << recursion_depth << std::endl;
 454         }
 455
 456         // Try filling with something
 457         str = get_legal_numbers(x, y);
 458         while (str.length()) {
 459                 i = get_random() % str.length();
 460
 461                 sudoku guess = *this;
 462                 guess.set(x, y, str[i]);
 463
 464                 if (verbose) {
 465                         //std::cout << "Trying number " << str[i] << " to "
 466                         //  << x << "." << y << std::endl;
 467                 }
 468
 469                 guess.recursion_depth = recursion_depth + 1;
 470
 471                 int can_solve;
 472                 guess = guess.fill_with_random(can_solve);
 473
 474                 //Did it solve?
 475                 if (can_solve) {
 476                         solvable = 1;
 477                         return guess;
 478                 }
 479
 480                 str.erase(i,1);
 481         }
 482
 483         // It didn't solve
 484         solvable = 0;
 485         return empty;
 486 }
 487
 488 int sudoku::used_numbers()
 489 {
 490         int x, y, count = 0;
 491         for (x = 0; x < 9; x++)
 492                 for (y = 0; y < 9; y++)
 493                         if (table[x][y] != EMPTY)
 494                                 count++;
 495         return count;
 496 }
 497
 498 static int done = 0;
 499
 500 sudoku sudoku::remove_randomly(int min_guesses, int depth)
 501 {
 502         int count = used_numbers();
 503         sudoku result;
 504         int stop = 0;
 505         sudoku work = *this;
 506
 507 #pragma omp parallel for firstprivate(stop, work)
 508         for (int i = 0; i < count; i++) {
 509                 int x, y;
 510                 sudoku tmp,tmp2;
 511                 std::vector<sudoku> results;
 512
 513                 if (done || stop)
 514                         continue;
 515
 516                 /* remove a number */
 517                 do {
 518                         x = get_random() % 9;
 519                         y = get_random() % 9;
 520                 } while(work.get(x,y) == EMPTY);
 521                 work.table[x][y] = EMPTY;
 522
 523                 //printf("Got now:\n");
 524                 //work.print();
 525
 526                 tmp2 = work;
 527                 /* solve it */
 528                 results = work.solve_all();
 529
 530                 /* Does it still have only one solution */
 531                 if (results.size() == 1 && !done) {
 532                         /* but not hard enough yet? */
 533                         if (work.guesses >= min_guesses) {
 534                                 /* It's good now */
 535                                 printf("%d, Good!\n", depth);
 536                                 result = work;
 537                                 done = 1;
 538                                 #pragma omp flush(done)
 539                         } else {
 540                                 printf("%2d, got only %3d guesses ", depth,
 541                                        work.guesses);
 542                                 tmp2.print_compact();
 543                         }
 544
 545                         if (!done) {
 546                                 work = tmp2;
 547                                 tmp = work.remove_randomly(min_guesses,
 548                                                    depth + 1);
 549
 550                                 /* test for emptiness */
 551                                 if (tmp.guesses == 0) {
 552                                         continue;
 553                                 }
 554
 555                                 if (tmp.guesses >= min_guesses) {
 556                                         result = tmp;
 557                                         done = 1;
 558                                         #pragma omp flush(done)
 559                                 } else {
 560                                         printf("%d: Guesses: %d, "
 561                                                "not good enough\n",
 562                                                depth, tmp2.guesses);
 563                                 }
 564                                 continue;
 565                         }
 566                 }
 567
 568                 if ((results.size() > 1) && !done) {
 569                         /* oops, removed too many */
 570                         sudoku empty;
 571                         //printf("%d, Got multiple results\n", depth);
 572                         result = empty;
 573                         stop = 1;
 574                 }
 575
 576                 if (results.empty() && !done) {
 577                         fprintf(stderr, "%d, Fail. This can't happen?\n",
 578                                 depth);
 579                         sudoku empty;
 580                         result = empty;
 581                 }
 582         }
 583         return result;
 584 }
 585
 586 int sudoku::generate(int min_guesses)
 587 {
 588         int solvable;
 589         sudoku tmp = fill_with_random(solvable);
 590
 591         if (!solvable)
 592                 return -1;
 593
 594         /* Right, we got it filled */
 595         tmp = tmp.remove_randomly(min_guesses, 0);
 596
 597         *this = tmp;
 598
 599         return solvable;
 600 }