Generates sudokus at desired difficulty level

[sudoku] / sudoku.cpp

diff --git a/sudoku.cpp b/sudoku.cpp
index a6dd2121a9c13876b9394b6c0934c46fa65e2cff..9279ffde4b5709c5dc6cb7aed4afe80ed9b44b80 100644 (file)
--- a/sudoku.cpp
+++ b/sudoku.cpp
@@ -84,7 +84,6 @@ int sudoku::set(const int col, const int row, const char val)
                return -1;
        }
 
-
        table[col][row] = val;
 
        return 0;
@@ -360,7 +359,8 @@ std::vector<sudoku> sudoku::solve_all()
                                  << recursion_depth << std::endl;
                }
                sudokus.push_back(*this);
-               print();
+               if (verbose)
+                       print();
                return sudokus;
        }
 
@@ -402,7 +402,8 @@ std::vector<sudoku> sudoku::solve_all()
                }
        }
 
-       std::cout << "Guesses: " << guesses << std::endl;
+       if (verbose)
+               std::cout << "Guesses: " << guesses << std::endl;
 
        // Return what was solved
        return sudokus;
@@ -481,13 +482,94 @@ sudoku sudoku::fill_with_random(int &solvable)
        return empty;
 }
 
+int sudoku::used_numbers()
+{
+       int x, y, count = 0;
+       for (x = 0; x < 9; x++)
+               for (y = 0; y < 9; y++)
+                       if (table[x][y] != EMPTY)
+                               count++;
+       return count;
+}
+
+sudoku sudoku::remove_randomly(int min_guesses, int depth)
+{
+       int x, y, i, count = used_numbers();
+       sudoku tmp = *this, tmp2;
+       std::vector<sudoku> results;
+
+       for (i = 0; i < count; i++) {
+               /* remove a number */
+               do {
+                       x = get_random() % 9;
+                       y = get_random() % 9;
+               } while(tmp.get(x,y) == EMPTY);
+               tmp.table[x][y] = EMPTY;
+
+               //printf("Got now:\n");
+               //tmp.print();
+
+               tmp2 = tmp;
+               /* solve it */
+               results = tmp.solve_all();
+
+               /* Does it still have only one solution */
+               if (results.size() == 1) {
+                       /* but not hard enough yet? */
+                       if (tmp.guesses >= min_guesses) {
+                               /* It's good now */
+                               printf("%d, Good!\n", depth);
+                               return tmp;
+                       } else {
+                               printf("%2d, got only %3d guesses\n", depth,
+                                      tmp.guesses);
+                       }
+
+                       tmp = tmp2;
+                       tmp2 = tmp.remove_randomly(min_guesses, depth + 1);
+
+                       /* test for emptiness */
+                       if (tmp2.guesses == 0) {
+                               continue;
+                       }
+
+                       if (tmp2.guesses >= min_guesses) {
+                               return tmp2;
+                       }
+
+                       printf("%d: Guesses: %d, not good enough\n", depth,
+                              tmp2.guesses);
+                       continue;
+               }
+
+               if (results.size() > 1) {
+                       /* oops, removed too many */
+                       sudoku empty;
+                       printf("%d, Got multiple results\n", depth);
+                       return empty;
+               }
+
+               if (results.empty()) {
+                       fprintf(stderr, "%d, Fail. This can't happen?\n",
+                               depth);
+                       sudoku empty;
+                       return empty;
+               }
+       }
+}
+
 int sudoku::generate(int min_guesses)
 {
        int solvable;
        sudoku tmp = fill_with_random(solvable);
 
-       if (solvable)
-               *this = tmp;
+       if (!solvable)
+               return -1;
+
+       /* Right, we got it filled */
+       tmp = tmp.remove_randomly(min_guesses, 0);
+
+       *this = tmp;
 
        return solvable;
 }