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::clone_to(sudoku &to)
 142 {
 143         sudoku clone;
 144         int x, y;
 145
 146         for (x = 0; x < 9; x++)
 147                 for (y = 0; y < 9; y++)
 148                         to.table[x][y] = table[x][y];
 149 }
 150
 151 std::string sudoku::get_row_contents(int row)
 152 {
 153         std::string s;
 154         int col;
 155
 156         for (col = 0; col < 9; col++) {
 157                 if (table[col][row] != EMPTY)
 158                         s += table[col][row];
 159         }
 160
 161         return s;
 162 }
 163
 164 std::string sudoku::get_col_contents(int col)
 165 {
 166         std::string s;
 167         int row;
 168
 169         for (row = 0; row < 9; row++) {
 170                 if (table[col][row] != EMPTY)
 171                         s += table[col][row];
 172         }
 173
 174         return s;
 175 }
 176
 177 std::string sudoku::get_block_contents(int col, int row)
 178 {
 179         std::string s;
 180         int x, y;
 181         char c;
 182
 183         if (col < 0 || col >= 9)
 184                 DPRINT "Aiee " << col << std::endl;
 185         if (row < 0 || row >= 9)
 186                 DPRINT "Aiee " << row << std::endl;
 187
 188         col = (col /= 3) * 3;
 189         row = (row /= 3) * 3;
 190
 191         for (y = 0; y < 3; y++)
 192                 for (x = 0; x < 3; x++) {
 193                         c = get(x + col, y + row);
 194                         if (c != EMPTY)
 195                                 s += c;
 196                 }
 197
 198         return s;
 199 }
 200
 201 static std::string exclude_common(std::string s1, std::string s2)
 202 {
 203         std::string::iterator a, b;
 204
 205 restart:
 206         for (a = s1.begin(); a != s1.end(); a++) {
 207                 for (b = s2.begin(); b != s2.end(); b++) {
 208                         if (*a == *b) {
 209                                 a = s1.erase(a);
 210                                 b = s2.erase(b);
 211                                 goto restart;
 212                         }
 213                 }
 214         }
 215         return s1;
 216 }
 217
 218 std::string sudoku::get_legal_numbers(int col, int row)
 219 {
 220         char val;
 221         std::string a, b, c, ret;
 222
 223         if (!check_validity(col, row)) {
 224                 DPRINT << "over here\n";
 225                 return NULL;
 226         }
 227
 228         val = get(col, row);
 229         if (val != EMPTY) {
 230                 return "0";
 231         }
 232
 233 //      std::cout << "[" << col << "." << row << "] ";
 234
 235         a = get_col_contents(col);
 236 //      std::cout << " col " << a;
 237
 238         b = get_row_contents(row);
 239 //      std::cout << " row " << b;
 240
 241         c = get_block_contents(col, row);
 242 //      std::cout << " block " << c;
 243
 244         ret = exclude_common("123456789", a);
 245         ret = exclude_common(ret, b);
 246         ret = exclude_common(ret, c);
 247
 248 //      std::cout << " legal " << ret << std::endl;
 249         return ret;
 250 }
 251
 252 int sudoku::fill_missing()
 253 {
 254         int x, y, solved = 0;
 255         std::string num;
 256
 257         for (y = 0; y < 9; y++)
 258                 for (x = 0; x < 9; x++) {
 259                                 num = get_legal_numbers(x, y);
 260                                 if ((num != "0") && (num.length() == 1)) {
 261                                         set(x, y, num[0]);
 262                                         solved++;
 263                         }
 264                 }
 265         if (verbose) {
 266                 //std::cout << "Solved " << solved << " numbers\n";
 267         }
 268
 269         return solved;
 270 }
 271
 272 int sudoku::get_best_guess(int &col, int &row)
 273 {
 274         int x, y;
 275         int min = 0, filled = 0, illegals = 0;
 276         std::string numbers;
 277
 278         /*
 279          * Initialize row and col with illegal values to spot possible
 280          * misuse
 281          */
 282         col = -1;
 283         row = -1;
 284
 285         for (y = 0; (y < 9) && !illegals; y++)
 286                 for (x = 0; x < 9; x++) {
 287                         numbers = get_legal_numbers(x, y);
 288
 289                         if (numbers == "0") {
 290                                 filled++;
 291                                 continue;
 292                         }
 293
 294                         if (numbers.length() == 0) {
 295                                 illegals++;
 296                                 break;
 297                         }
 298
 299                         if (!min) {
 300                                 min = numbers.length();
 301                                 col = x;
 302                                 row = y;
 303                                 continue;
 304                         }
 305
 306                         if ((int)numbers.length() < min) {
 307                                 min = numbers.length();
 308                                 col = x;
 309                                 row = y;
 310                                 if (min == 1)
 311                                         return min;
 312                         }
 313 //                      std::cout <<  x << "." << y << ": " << " min "
 314 //                                << numbers << col << "." << row << std::endl;
 315                 }
 316
 317         if ((!min && !filled) || illegals) {
 318 //              DPRINT << "Is this sudoku has no solutions?\n";
 319                 return -1;
 320         }
 321
 322         if (!min && (filled == 99)) {
 323                 DPRINT << "This sudoku is solved\n";
 324                 return 0;
 325         }
 326
 327         return min;
 328 }
 329
 330 std::vector<sudoku> sudoku::solve_all()
 331 {
 332         int x, y, i, j, ret;
 333         std::string str;
 334         std::vector<sudoku> sudokus;
 335
 336         // Fill in as much as possible
 337         do {
 338                 if (verbose) {
 339                         std::cout << std::endl;
 340                         print();
 341                 }
 342         } while (fill_missing() != 0);
 343
 344         ret = get_best_guess(x, y);
 345
 346         // Did we solve it yet?
 347         switch (ret) {
 348         case -1:
 349                 // Unsolvable
 350                 if (verbose) {
 351                         std::cout << "This is unsolvable, recursion: "
 352                                   << recursion_depth << std::endl;
 353                 }
 354                 return sudokus;
 355         case 0:
 356                 // Solved
 357                 if (verbose) {
 358                         std::cout << "Solution found , recursion: "
 359                                   << recursion_depth << std::endl;
 360                 }
 361                 sudokus.push_back(*this);
 362                 if (verbose)
 363                         print();
 364                 return sudokus;
 365         }
 366
 367         if (verbose) {
 368                 std::cout << "Not solved yet, guessing at depth "
 369                           << recursion_depth << std::endl;
 370         }
 371
 372         // Try guessim something
 373         str = get_legal_numbers(x, y);
 374         for (i = 0; i < (int)str.length(); i++) {
 375                 std::vector<sudoku> results;
 376
 377                 sudoku guess = *this;
 378                 guesses++;
 379
 380                 if (verbose) {
 381                         std::cout << "Guessing number " << str[i] << " to "
 382                                   << x << "." << y << std::endl;
 383                 }
 384
 385                 guess.set(x, y, str[i]);
 386                 guess.recursion_depth = recursion_depth + 1;
 387                 guess.guesses = 0;
 388
 389                 results = guess.solve_all();
 390                 guesses += guess.guesses;
 391
 392                 //Did it solve?
 393                 if (!results.empty()) {
 394 /*                      printf("Got %d solutions, guessed %d: %s\n",
 395                                (int)results.size(), (int)str.size(),
 396                                str.c_str());*/
 397
 398                         for(j = 0;j < (int)results.size(); j++) {
 399                                 sudokus.push_back(results.at(j));
 400                                 guesses += results.at(j).guesses;
 401                         }
 402                 }
 403         }
 404
 405         if (verbose)
 406                 std::cout << "Guesses: " << guesses << std::endl;
 407
 408         // Return what was solved
 409         return sudokus;
 410 }
 411
 412 sudoku sudoku::fill_with_random(int &solvable)
 413 {
 414         int x, y, i, ret;
 415         std::string str;
 416         sudoku empty;
 417
 418         // Fill in as much as possible
 419         do {
 420                 if (verbose) {
 421                         //std::cout << std::endl;
 422                         //print();
 423                 }
 424         } while (fill_missing() != 0);
 425
 426         ret = get_best_guess(x, y);
 427
 428         // Did we fill it yet?
 429         switch (ret) {
 430         case -1:
 431                 // Unsolvable
 432                 solvable = 0;
 433                 if (verbose) {
 434                         //std::cout << "This is unsolvable, recursion: "
 435                         //  << recursion_depth << std::endl;
 436                 }
 437                 return empty;
 438         case 0:
 439                 // Solved
 440                 solvable = 1;
 441                 if (verbose) {
 442                         //std::cout << "Solution found , recursion: "
 443                         //  << recursion_depth << std::endl;
 444                 }
 445                 return *this;
 446         }
 447
 448         if (verbose) {
 449                 //std::cout << "Not solved yet, guessing at depth "
 450                 //  << recursion_depth << std::endl;
 451         }
 452
 453         // Try filling with something
 454         str = get_legal_numbers(x, y);
 455         while (str.length()) {
 456                 i = get_random() % str.length();
 457
 458                 sudoku guess = *this;
 459                 guess.set(x, y, str[i]);
 460
 461                 if (verbose) {
 462                         //std::cout << "Trying number " << str[i] << " to "
 463                         //  << x << "." << y << std::endl;
 464                 }
 465
 466                 guess.recursion_depth = recursion_depth + 1;
 467
 468                 int can_solve;
 469                 guess = guess.fill_with_random(can_solve);
 470
 471                 //Did it solve?
 472                 if (can_solve) {
 473                         solvable = 1;
 474                         return guess;
 475                 }
 476
 477                 str.erase(i,1);
 478         }
 479
 480         // It didn't solve
 481         solvable = 0;
 482         return empty;
 483 }
 484
 485 int sudoku::used_numbers()
 486 {
 487         int x, y, count = 0;
 488         for (x = 0; x < 9; x++)
 489                 for (y = 0; y < 9; y++)
 490                         if (table[x][y] != EMPTY)
 491                                 count++;
 492         return count;
 493 }
 494
 495 sudoku sudoku::remove_randomly(int min_guesses, int depth)
 496 {
 497         int x, y, i, count = used_numbers();
 498         sudoku tmp = *this, tmp2;
 499         std::vector<sudoku> results;
 500
 501         for (i = 0; i < count; i++) {
 502                 /* remove a number */
 503                 do {
 504                         x = get_random() % 9;
 505                         y = get_random() % 9;
 506                 } while(tmp.get(x,y) == EMPTY);
 507                 tmp.table[x][y] = EMPTY;
 508
 509                 //printf("Got now:\n");
 510                 //tmp.print();
 511
 512                 tmp2 = tmp;
 513                 /* solve it */
 514                 results = tmp.solve_all();
 515
 516                 /* Does it still have only one solution */
 517                 if (results.size() == 1) {
 518                         /* but not hard enough yet? */
 519                         if (tmp.guesses >= min_guesses) {
 520                                 /* It's good now */
 521                                 printf("%d, Good!\n", depth);
 522                                 return tmp;
 523                         } else {
 524                                 printf("%2d, got only %3d guesses\n", depth,
 525                                        tmp.guesses);
 526                         }
 527
 528                         tmp = tmp2;
 529                         tmp2 = tmp.remove_randomly(min_guesses, depth + 1);
 530
 531                         /* test for emptiness */
 532                         if (tmp2.guesses == 0) {
 533                                 continue;
 534                         }
 535
 536                         if (tmp2.guesses >= min_guesses) {
 537                                 return tmp2;
 538                         }
 539
 540                         printf("%d: Guesses: %d, not good enough\n", depth,
 541                                tmp2.guesses);
 542                         continue;
 543                 }
 544
 545                 if (results.size() > 1) {
 546                         /* oops, removed too many */
 547                         sudoku empty;
 548                         printf("%d, Got multiple results\n", depth);
 549                         return empty;
 550                 }
 551
 552                 if (results.empty()) {
 553                         fprintf(stderr, "%d, Fail. This can't happen?\n",
 554                                 depth);
 555                         sudoku empty;
 556                         return empty;
 557                 }
 558         }
 559 }
 560
 561 int sudoku::generate(int min_guesses)
 562 {
 563         int solvable;
 564         sudoku tmp = fill_with_random(solvable);
 565
 566         if (!solvable)
 567                 return -1;
 568
 569         /* Right, we got it filled */
 570         tmp = tmp.remove_randomly(min_guesses, 0);
 571
 572         *this = tmp;
 573
 574         return solvable;
 575 }