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
  88         table[col][row] = val;
  89
  90         return 0;
  91 }
  92
  93 int sudoku::str_to_row(const int row, const std::string &str)
  94 {
  95         unsigned int i, col = 0;
  96         char chr;
  97
  98         if (row < 0 || row >= 9) {
  99                 DPRINT << "Illegal row " << row << std::endl;
 100                 return -1;
 101         }
 102
 103         for (i = 0; i < str.length(); i++) {
 104                 chr = str.at(i);
 105
 106                 if ((chr == '?') ||
 107                     (chr == '_') ||
 108                     (chr == '.')){
 109                         col++;
 110                         continue;
 111                 }
 112
 113                 /* Ignore non-numbers */
 114                 if (chr < '1' || chr > '9')
 115                         continue;
 116
 117                 set(col++, row, chr);
 118                 if (col >= 9)
 119                         break;
 120         }
 121         return 0;
 122 }
 123
 124 void sudoku::print(void)
 125 {
 126         int x,y;
 127
 128         printf("+-------+------+--------+\n");
 129         for (y = 0; y < 9; y++) {
 130                 printf("| ");
 131                 for (x = 0; x < 9; x++) {
 132                         printf("%c ", table[x][y]);
 133                         if (!((x  + 1)% 3))
 134                                 printf("| ");
 135                 }
 136                 printf("\n");
 137                 if (!((y + 1) % 3))
 138                         printf("+-------+-------+-------+\n");
 139         }
 140 }
 141
 142 void sudoku::clone_to(sudoku &to)
 143 {
 144         sudoku clone;
 145         int x, y;
 146
 147         for (x = 0; x < 9; x++)
 148                 for (y = 0; y < 9; y++)
 149                         to.table[x][y] = table[x][y];
 150 }
 151
 152 std::string sudoku::get_row_contents(int row)
 153 {
 154         std::string s;
 155         int col;
 156
 157         for (col = 0; col < 9; col++) {
 158                 if (table[col][row] != EMPTY)
 159                         s += table[col][row];
 160         }
 161
 162         return s;
 163 }
 164
 165 std::string sudoku::get_col_contents(int col)
 166 {
 167         std::string s;
 168         int row;
 169
 170         for (row = 0; row < 9; row++) {
 171                 if (table[col][row] != EMPTY)
 172                         s += table[col][row];
 173         }
 174
 175         return s;
 176 }
 177
 178 std::string sudoku::get_block_contents(int col, int row)
 179 {
 180         std::string s;
 181         int x, y;
 182         char c;
 183
 184         if (col < 0 || col >= 9)
 185                 DPRINT "Aiee " << col << std::endl;
 186         if (row < 0 || row >= 9)
 187                 DPRINT "Aiee " << row << std::endl;
 188
 189         col = (col /= 3) * 3;
 190         row = (row /= 3) * 3;
 191
 192         for (y = 0; y < 3; y++)
 193                 for (x = 0; x < 3; x++) {
 194                         c = get(x + col, y + row);
 195                         if (c != EMPTY)
 196                                 s += c;
 197                 }
 198
 199         return s;
 200 }
 201
 202 static std::string exclude_common(std::string s1, std::string s2)
 203 {
 204         std::string::iterator a, b;
 205
 206 restart:
 207         for (a = s1.begin(); a != s1.end(); a++) {
 208                 for (b = s2.begin(); b != s2.end(); b++) {
 209                         if (*a == *b) {
 210                                 a = s1.erase(a);
 211                                 b = s2.erase(b);
 212                                 goto restart;
 213                         }
 214                 }
 215         }
 216         return s1;
 217 }
 218
 219 std::string sudoku::get_legal_numbers(int col, int row)
 220 {
 221         char val;
 222         std::string a, b, c, ret;
 223
 224         if (!check_validity(col, row)) {
 225                 DPRINT << "over here\n";
 226                 return NULL;
 227         }
 228
 229         val = get(col, row);
 230         if (val != EMPTY) {
 231                 return "0";
 232         }
 233
 234 //      std::cout << "[" << col << "." << row << "] ";
 235
 236         a = get_col_contents(col);
 237 //      std::cout << " col " << a;
 238
 239         b = get_row_contents(row);
 240 //      std::cout << " row " << b;
 241
 242         c = get_block_contents(col, row);
 243 //      std::cout << " block " << c;
 244
 245         ret = exclude_common("123456789", a);
 246         ret = exclude_common(ret, b);
 247         ret = exclude_common(ret, c);
 248
 249 //      std::cout << " legal " << ret << std::endl;
 250         return ret;
 251 }
 252
 253 int sudoku::fill_missing()
 254 {
 255         int x, y, solved = 0;
 256         std::string num;
 257
 258         for (y = 0; y < 9; y++)
 259                 for (x = 0; x < 9; x++) {
 260                                 num = get_legal_numbers(x, y);
 261                                 if ((num != "0") && (num.length() == 1)) {
 262                                         set(x, y, num[0]);
 263                                         solved++;
 264                         }
 265                 }
 266         if (verbose) {
 267                 //std::cout << "Solved " << solved << " numbers\n";
 268         }
 269
 270         return solved;
 271 }
 272
 273 int sudoku::get_best_guess(int &col, int &row)
 274 {
 275         int x, y;
 276         int min = 0, filled = 0, illegals = 0;
 277         std::string numbers;
 278
 279         /*
 280          * Initialize row and col with illegal values to spot possible
 281          * misuse
 282          */
 283         col = -1;
 284         row = -1;
 285
 286         for (y = 0; (y < 9) && !illegals; y++)
 287                 for (x = 0; x < 9; x++) {
 288                         numbers = get_legal_numbers(x, y);
 289
 290                         if (numbers == "0") {
 291                                 filled++;
 292                                 continue;
 293                         }
 294
 295                         if (numbers.length() == 0) {
 296                                 illegals++;
 297                                 break;
 298                         }
 299
 300                         if (!min) {
 301                                 min = numbers.length();
 302                                 col = x;
 303                                 row = y;
 304                                 continue;
 305                         }
 306
 307                         if ((int)numbers.length() < min) {
 308                                 min = numbers.length();
 309                                 col = x;
 310                                 row = y;
 311                                 if (min == 1)
 312                                         return min;
 313                         }
 314 //                      std::cout <<  x << "." << y << ": " << " min "
 315 //                                << numbers << col << "." << row << std::endl;
 316                 }
 317
 318         if ((!min && !filled) || illegals) {
 319 //              DPRINT << "Is this sudoku has no solutions?\n";
 320                 return -1;
 321         }
 322
 323         if (!min && (filled == 99)) {
 324                 DPRINT << "This sudoku is solved\n";
 325                 return 0;
 326         }
 327
 328         return min;
 329 }
 330
 331 std::vector<sudoku> sudoku::solve_all()
 332 {
 333         int x, y, i, j, ret;
 334         std::string str;
 335         std::vector<sudoku> sudokus;
 336
 337         // Fill in as much as possible
 338         do {
 339                 if (verbose) {
 340                         std::cout << std::endl;
 341                         print();
 342                 }
 343         } while (fill_missing() != 0);
 344
 345         ret = get_best_guess(x, y);
 346
 347         // Did we solve it yet?
 348         switch (ret) {
 349         case -1:
 350                 // Unsolvable
 351                 if (verbose) {
 352                         std::cout << "This is unsolvable, recursion: "
 353                                   << recursion_depth << std::endl;
 354                 }
 355                 return sudokus;
 356         case 0:
 357                 // Solved
 358                 if (verbose) {
 359                         std::cout << "Solution found , recursion: "
 360                                   << recursion_depth << std::endl;
 361                 }
 362                 sudokus.push_back(*this);
 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         std::cout << "Guesses: " << guesses << std::endl;
 406
 407         // Return what was solved
 408         return sudokus;
 409 }
 410
 411 sudoku sudoku::fill_with_random(int &solvable)
 412 {
 413         int x, y, i, ret;
 414         std::string str;
 415         sudoku empty;
 416
 417         // Fill in as much as possible
 418         do {
 419                 if (verbose) {
 420                         //std::cout << std::endl;
 421                         //print();
 422                 }
 423         } while (fill_missing() != 0);
 424
 425         ret = get_best_guess(x, y);
 426
 427         // Did we fill it yet?
 428         switch (ret) {
 429         case -1:
 430                 // Unsolvable
 431                 solvable = 0;
 432                 if (verbose) {
 433                         //std::cout << "This is unsolvable, recursion: "
 434                         //  << recursion_depth << std::endl;
 435                 }
 436                 return empty;
 437         case 0:
 438                 // Solved
 439                 solvable = 1;
 440                 if (verbose) {
 441                         //std::cout << "Solution found , recursion: "
 442                         //  << recursion_depth << std::endl;
 443                 }
 444                 return *this;
 445         }
 446
 447         if (verbose) {
 448                 //std::cout << "Not solved yet, guessing at depth "
 449                 //  << recursion_depth << std::endl;
 450         }
 451
 452         // Try filling with something
 453         str = get_legal_numbers(x, y);
 454         while (str.length()) {
 455                 i = get_random() % str.length();
 456
 457                 sudoku guess = *this;
 458                 guess.set(x, y, str[i]);
 459
 460                 if (verbose) {
 461                         //std::cout << "Trying number " << str[i] << " to "
 462                         //  << x << "." << y << std::endl;
 463                 }
 464
 465                 guess.recursion_depth = recursion_depth + 1;
 466
 467                 int can_solve;
 468                 guess = guess.fill_with_random(can_solve);
 469
 470                 //Did it solve?
 471                 if (can_solve) {
 472                         solvable = 1;
 473                         return guess;
 474                 }
 475
 476                 str.erase(i,1);
 477         }
 478
 479         // It didn't solve
 480         solvable = 0;
 481         return empty;
 482 }
 483
 484 int sudoku::generate(int min_guesses)
 485 {
 486         int solvable;
 487         sudoku tmp = fill_with_random(solvable);
 488
 489         if (solvable)
 490                 *this = tmp;
 491
 492         return solvable;
 493 }