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
   7 #define EMPTY ' '
   8
   9 int guesses = 0;
  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 }
  22
  23 sudoku::~sudoku()
  24 {
  25 }
  26
  27 static int check_validity(const int col, const int row)
  28 {
  29         if (col < 0 || col >= 9) {
  30                 DPRINT << "Invalid column: " << col << std::endl;
  31                 return 0;
  32         }
  33
  34         if (row < 0 || row >= 9) {
  35                 DPRINT << "Invalid row: " << row << std::endl;
  36                 return 0;
  37         }
  38         return 1;
  39 }
  40
  41 char sudoku::get(const int col, const int row)
  42 {
  43         if (!check_validity(row, col)) {
  44                 DPRINT << "over here\n";
  45                 return 0;
  46         }
  47
  48         return table[col][row];
  49 }
  50
  51 int sudoku::set(const int col, const int row, const char val)
  52 {
  53         std::string str;
  54
  55         if (!check_validity(col, row)) {
  56                 DPRINT << "over here\n";
  57                 return -1;
  58         }
  59
  60         if (table[col][row] != EMPTY) {
  61                 DPRINT << "Assigning value to a non-empty slot\n";
  62                 return -1;
  63         }
  64
  65         str = get_col_contents(col);
  66         if (str.find(val, 0) != std::string::npos) {
  67                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  68                        << val << std::endl;
  69                 return -1;
  70         }
  71
  72         str = get_row_contents(row);
  73         if (str.find(val, 0) != std::string::npos) {
  74                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  75                        << val << std::endl;
  76                 return -1;
  77         }
  78
  79         str = get_block_contents(col, row);
  80         if (str.find(val, 0) != std::string::npos) {
  81                 DPRINT << "Illegal assignment " << col << "." << row << ": "
  82                        << val << std::endl;
  83                 return -1;
  84         }
  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
 202
 203 static std::string exclude_common(std::string s1, std::string s2)
 204 {
 205         std::string::iterator a, b;
 206
 207 restart:
 208         for (a = s1.begin(); a != s1.end(); a++) {
 209                 for (b = s2.begin(); b != s2.end(); b++) {
 210                         if (*a == *b) {
 211                                 a = s1.erase(a);
 212                                 b = s2.erase(b);
 213                                 goto restart;
 214                         }
 215                 }
 216         }
 217         return s1;
 218 }
 219
 220 std::string sudoku::get_legal_numbers(int col, int row)
 221 {
 222         char val;
 223         std::string a, b, c, ret;
 224
 225         if (!check_validity(col, row)) {
 226                 DPRINT << "over here\n";
 227                 return NULL;
 228         }
 229
 230         val = get(col, row);
 231         if (val != EMPTY) {
 232                 return "0";
 233         }
 234
 235 //      std::cout << "[" << col << "." << row << "] ";
 236
 237         a = get_col_contents(col);
 238 //      std::cout << " col " << a;
 239
 240         b = get_row_contents(row);
 241 //      std::cout << " row " << b;
 242
 243         c = get_block_contents(col, row);
 244 //      std::cout << " block " << c;
 245
 246         ret = exclude_common("123456789", a);
 247         ret = exclude_common(ret, b);
 248         ret = exclude_common(ret, c);
 249
 250 //      std::cout << " legal " << ret << std::endl;
 251         return ret;
 252 }
 253
 254 int sudoku::fill_missing()
 255 {
 256         int x, y, solved = 0;
 257         std::string num;
 258
 259         for (y = 0; y < 9; y++)
 260                 for (x = 0; x < 9; x++) {
 261                                 num = get_legal_numbers(x, y);
 262                                 if ((num != "0") && (num.length() == 1)) {
 263                                         set(x, y, num[0]);
 264                                         solved++;
 265                         }
 266                 }
 267         if (verbose) {
 268                 std::cout << "Solved " << solved << " numbers\n";
 269         }
 270
 271         return solved;
 272 }
 273
 274 int sudoku::get_best_guess(int &col, int &row)
 275 {
 276         int x, y;
 277         int min = 0, filled = 0, illegals = 0;
 278         std::string numbers;
 279
 280         /*
 281          * Initialize row and col with illegal values to spot possible
 282          * misuse
 283          */
 284         col = -1;
 285         row = -1;
 286
 287         for (y = 0; (y < 9) && !illegals; y++)
 288                 for (x = 0; x < 9; x++) {
 289                         numbers = get_legal_numbers(x, y);
 290
 291                         if (numbers == "0") {
 292                                 filled++;
 293                                 continue;
 294                         }
 295
 296                         if (numbers.length() == 0) {
 297                                 illegals++;
 298                                 break;
 299                         }
 300
 301                         if (!min) {
 302                                 min = numbers.length();
 303                                 col = x;
 304                                 row = y;
 305                                 continue;
 306                         }
 307
 308                         if ((int)numbers.length() < min) {
 309                                 min = numbers.length();
 310                                 col = x;
 311                                 row = y;
 312                                 if (min == 1)
 313                                         return min;
 314                         }
 315 //                      std::cout <<  x << "." << y << ": " << " min "
 316 //                                << numbers << col << "." << row << std::endl;
 317                 }
 318
 319         if ((!min && !filled) || illegals) {
 320 //              DPRINT << "Is this sudoku has no solutions?\n";
 321                 return -1;
 322         }
 323
 324         if (!min && (filled == 99)) {
 325                 DPRINT << "This sudoku is solved\n";
 326                 return 0;
 327         }
 328
 329         return min;
 330 }
 331
 332 sudoku sudoku::solve(int &solvable)
 333 {
 334         int x, y, i, ret;
 335         std::string str;
 336         sudoku empty;
 337
 338         // Fill in as much as possible
 339         do {
 340                 if (verbose) {
 341                         std::cout << std::endl;
 342                         print();
 343                 }
 344         } while (fill_missing() != 0);
 345
 346         ret = get_best_guess(x, y);
 347
 348         // Did we solve it yet?
 349         switch (ret) {
 350         case -1:
 351                 // Unsolvable
 352                 solvable = 0;
 353                 if (verbose) {
 354                         std::cout << "This is unsolvable, recursion: "
 355                                   << recursion_depth << std::endl;
 356                 }
 357                 return empty;
 358         case 0:
 359                 // Solved
 360                 solvable = 1;
 361                 if (verbose) {
 362                         std::cout << "Solution found , recursion: "
 363                                   << recursion_depth << std::endl;
 364                 }
 365                 return *this;
 366         }
 367
 368         if (verbose) {
 369                 std::cout << "Not solved yet, guessing at depth "
 370                           << recursion_depth << std::endl;
 371         }
 372
 373         // Try guessim something
 374         str = get_legal_numbers(x, y);
 375         for (i = 0; i < (int)str.length(); i++) {
 376
 377                 sudoku guess = *this;
 378                 guess.set(x, y, str[i]);
 379
 380                 if (verbose) {
 381                         std::cout << "Guessing number " << str[i] << " to "
 382                                   << x << "." << y << std::endl;
 383                 }
 384
 385                 guess.recursion_depth = recursion_depth + 1;
 386
 387                 int can_solve;
 388                 guess = guess.solve(can_solve);
 389
 390                 //Did it solve?
 391                 if (can_solve)
 392                         return guess;
 393         }
 394
 395         // It didn't solve
 396         solvable = 0;
 397         return empty;
 398 }
 399
 400 std::vector<sudoku> sudoku::solve_all()
 401 {
 402         int x, y, i, j, ret;
 403         std::string str;
 404         std::vector<sudoku> sudokus;
 405
 406         // Fill in as much as possible
 407         do {
 408                 if (verbose) {
 409                         std::cout << std::endl;
 410                         print();
 411                 }
 412         } while (fill_missing() != 0);
 413
 414         ret = get_best_guess(x, y);
 415
 416         // Did we solve it yet?
 417         switch (ret) {
 418         case -1:
 419                 // Unsolvable
 420                 if (verbose) {
 421                         std::cout << "This is unsolvable, recursion: "
 422                                   << recursion_depth << std::endl;
 423                 }
 424                 return sudokus;
 425         case 0:
 426                 // Solved
 427                 if (verbose) {
 428                         std::cout << "Solution found , recursion: "
 429                                   << recursion_depth << std::endl;
 430                 }
 431                 sudokus.push_back(*this);
 432                 print();
 433                 return sudokus;
 434         }
 435
 436         if (verbose) {
 437                 std::cout << "Not solved yet, guessing at depth "
 438                           << recursion_depth << std::endl;
 439         }
 440
 441         // Try guessim something
 442         str = get_legal_numbers(x, y);
 443         for (i = 0; i < (int)str.length(); i++) {
 444                 std::vector<sudoku> results;
 445
 446                 sudoku guess = *this;
 447                 guesses++;
 448
 449                 if (verbose) {
 450                         std::cout << "Guessing number " << str[i] << " to "
 451                                   << x << "." << y << std::endl;
 452                 }
 453
 454                 guess.set(x, y, str[i]);
 455                 guess.recursion_depth = recursion_depth + 1;
 456
 457                 results = guess.solve_all();
 458
 459                 //Did it solve?
 460                 if (!results.empty()) {
 461 /*                      printf("Got %d solutions, guessed %d: %s\n",
 462                                (int)results.size(), (int)str.size(),
 463                                str.c_str());*/
 464
 465                         for(j = 0;j < (int)results.size(); j++)
 466                                 sudokus.push_back(results.at(j));
 467                 }
 468         }
 469
 470         // Return what was solved
 471         return sudokus;
 472 }
 473