random.cpp: Return better random numbers

[sudoku] / sudoku.cpp

diff --git a/sudoku.cpp b/sudoku.cpp
index 9279ffde4b5709c5dc6cb7aed4afe80ed9b44b80..76144bfcc64561952905b51354dd73b007081a92 100644 (file)
--- a/sudoku.cpp
+++ b/sudoku.cpp
@@ -122,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++) {
@@ -138,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)
@@ -492,70 +495,92 @@ int sudoku::used_numbers()
        return count;
 }
 
+static int done = 0;
+
 sudoku sudoku::remove_randomly(int min_guesses, int depth)
 {
-       int x, y, i, count = used_numbers();
-       sudoku tmp = *this, tmp2;
-       std::vector<sudoku> results;
+       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;
 
-       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;
+               } while(work.get(x,y) == EMPTY);
+               work.table[x][y] = EMPTY;
 
                //printf("Got now:\n");
-               //tmp.print();
+               //work.print();
 
-               tmp2 = tmp;
+               tmp2 = work;
                /* solve it */
-               results = tmp.solve_all();
+               results = work.solve_all();
 
                /* Does it still have only one solution */
-               if (results.size() == 1) {
+               if (results.size() == 1 && !done) {
                        /* but not hard enough yet? */
-                       if (tmp.guesses >= min_guesses) {
+                       if (work.guesses >= min_guesses) {
                                /* It's good now */
                                printf("%d, Good!\n", depth);
-                               return tmp;
+                               result = work;
+                               done = 1;
+                               #pragma omp flush(done)
                        } else {
-                               printf("%2d, got only %3d guesses\n", depth,
-                                      tmp.guesses);
+                               printf("%2d, got only %3d guesses ", depth,
+                                      work.guesses);
+                               tmp2.print_compact();
                        }
 
-                       tmp = tmp2;
-                       tmp2 = tmp.remove_randomly(min_guesses, depth + 1);
-
-                       /* test for emptiness */
-                       if (tmp2.guesses == 0) {
+                       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 (tmp2.guesses >= min_guesses) {
-                               return tmp2;
-                       }
-
-                       printf("%d: Guesses: %d, not good enough\n", depth,
-                              tmp2.guesses);
-                       continue;
                }
 
-               if (results.size() > 1) {
+               if ((results.size() > 1) && !done) {
                        /* oops, removed too many */
                        sudoku empty;
-                       printf("%d, Got multiple results\n", depth);
-                       return empty;
+                       //printf("%d, Got multiple results\n", depth);
+                       result = empty;
+                       stop = 1;
                }
 
-               if (results.empty()) {
+               if (results.empty() && !done) {
                        fprintf(stderr, "%d, Fail. This can't happen?\n",
                                depth);
                        sudoku empty;
-                       return empty;
+                       result = empty;
                }
        }
+       return result;
 }
 
 int sudoku::generate(int min_guesses)