random.cpp: Return better random numbers

[sudoku] / sudoku.cpp

diff --git a/sudoku.cpp b/sudoku.cpp
index a6dd2121a9c13876b9394b6c0934c46fa65e2cff..76144bfcc64561952905b51354dd73b007081a92 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;
@@ -123,7 +122,7 @@ int sudoku::str_to_row(const int row, const std::string &str)
 
 void sudoku::print(void)
 {
-       int x,y;
+       int x, y;
 
        printf("+-------+------+--------+\n");
        for (y = 0; y < 9; y++) {
@@ -139,14 +138,17 @@ void sudoku::print(void)
        }
 }
 
-void sudoku::clone_to(sudoku &to)
+void sudoku::print_compact(void)
 {
-       sudoku clone;
-       int x, y;
+       int x, y, i = 0;
+       char str[82];
+       str[81] = 0;
 
-       for (x = 0; x < 9; x++)
-               for (y = 0; y < 9; y++)
-                       to.table[x][y] = table[x][y];
+       for (y = 0; y < 9; y++)
+               for (x = 0; x < 9; x++, i++)
+                       str[i] = table[x][y] != EMPTY ? table[x][y] : '.';
+
+       printf("%s\n", str);
 }
 
 std::string sudoku::get_row_contents(int row)
@@ -360,7 +362,8 @@ std::vector<sudoku> sudoku::solve_all()
                                  << recursion_depth << std::endl;
                }
                sudokus.push_back(*this);
-               print();
+               if (verbose)
+                       print();
                return sudokus;
        }
 
@@ -402,7 +405,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 +485,116 @@ 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;
+}
+
+static int done = 0;
+
+sudoku sudoku::remove_randomly(int min_guesses, int depth)
+{
+       int count = used_numbers();
+       sudoku result;
+       int stop = 0;
+       sudoku work = *this;
+
+#pragma omp parallel for firstprivate(stop, work)
+       for (int i = 0; i < count; i++) {
+               int x, y;
+               sudoku tmp,tmp2;
+               std::vector<sudoku> results;
+
+               if (done || stop)
+                       continue;
+
+               /* remove a number */
+               do {
+                       x = get_random() % 9;
+                       y = get_random() % 9;
+               } while(work.get(x,y) == EMPTY);
+               work.table[x][y] = EMPTY;
+
+               //printf("Got now:\n");
+               //work.print();
+
+               tmp2 = work;
+               /* solve it */
+               results = work.solve_all();
+
+               /* Does it still have only one solution */
+               if (results.size() == 1 && !done) {
+                       /* but not hard enough yet? */
+                       if (work.guesses >= min_guesses) {
+                               /* It's good now */
+                               printf("%d, Good!\n", depth);
+                               result = work;
+                               done = 1;
+                               #pragma omp flush(done)
+                       } else {
+                               printf("%2d, got only %3d guesses ", depth,
+                                      work.guesses);
+                               tmp2.print_compact();
+                       }
+
+                       if (!done) {
+                               work = tmp2;
+                               tmp = work.remove_randomly(min_guesses,
+                                                  depth + 1);
+
+                               /* test for emptiness */
+                               if (tmp.guesses == 0) {
+                                       continue;
+                               }
+
+                               if (tmp.guesses >= min_guesses) {
+                                       result = tmp;
+                                       done = 1;
+                                       #pragma omp flush(done)
+                               } else {
+                                       printf("%d: Guesses: %d, "
+                                              "not good enough\n",
+                                              depth, tmp2.guesses);
+                               }
+                               continue;
+                       }
+               }
+
+               if ((results.size() > 1) && !done) {
+                       /* oops, removed too many */
+                       sudoku empty;
+                       //printf("%d, Got multiple results\n", depth);
+                       result = empty;
+                       stop = 1;
+               }
+
+               if (results.empty() && !done) {
+                       fprintf(stderr, "%d, Fail. This can't happen?\n",
+                               depth);
+                       sudoku empty;
+                       result = empty;
+               }
+       }
+       return result;
+}
+
 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;
 }