Generator: First version that searches sudokus in parallel threads

diff --git a/Makefile b/Makefile
index a5d8c8178f1edfa21371e442cfadc9643566bbf9..0a07af4f8c3d56fa4fc0bf830d01eac960fabee3 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,6 @@
 CC=g++
-LD=ld
-CFLAGS=-Wall -O2 -g
+CFLAGS=-Wall -O2 -g -fopenmp
+LDFLAGS=-fopenmp
 
 SOLVER_OBJS= solver.o sudoku.o random.o
 GENERATOR_OBJS= generator.o sudoku.o random.o
@@ -8,16 +8,16 @@ GENERATOR_OBJS= generator.o sudoku.o random.o
 all: sudokusolver sudokugenerator
 
 sudokusolver: $(SOLVER_OBJS)
-       $(CC) $(SOLVER_OBJS) -o sudokusolver
+       $(CC) $(LDFLAGS) $(SOLVER_OBJS) -o sudokusolver
 
 sudokugenerator: $(GENERATOR_OBJS)
-       $(CC) $(GENERATOR_OBJS) -o sudokugenerator
+       $(CC) $(LDFLAGS) $(GENERATOR_OBJS) -o sudokugenerator
 
-cpp.o:
+%.o: %.cpp
        $(CC) -MMD -MF .$@.d $(CFLAGS) -c $< -o $@
 
 clean:
-       rm -rfv *~ *.o *.d sudokusolver
+       rm -rfv *~ *.o .*.d sudokusolver
 
 TAGS:
        etags *.[ch]

diff --git a/sudoku.cpp b/sudoku.cpp
index 9279ffde4b5709c5dc6cb7aed4afe80ed9b44b80..4d5d288dcd7bf44f74176f7b05992dbd131c0e64 100644 (file)
--- a/sudoku.cpp
+++ b/sudoku.cpp
@@ -492,13 +492,22 @@ 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;
+
+#pragma omp parallel for
+       for (int i = 0; i < count; i++) {
+               int x, y;
+               sudoku tmp = *this, tmp2;
+               std::vector<sudoku> results;
+
+               if (done)
+                       continue;
 
-       for (i = 0; i < count; i++) {
                /* remove a number */
                do {
                        x = get_random() % 9;
@@ -514,48 +523,60 @@ sudoku sudoku::remove_randomly(int min_guesses, int depth)
                results = tmp.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) {
                                /* It's good now */
                                printf("%d, Good!\n", depth);
-                               return tmp;
+                               result = tmp;
+                               done = 1;
+                               #pragma omp flush(done)
                        } 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) {
+                       if (!done) {
+                               tmp = tmp2;
+                               tmp2 = tmp.remove_randomly(min_guesses,
+                                                  depth + 1);
+
+                               /* test for emptiness */
+                               if (tmp2.guesses == 0) {
+                                       continue;
+                               }
+
+                               if (tmp2.guesses >= min_guesses) {
+                                       result = tmp2;
+                                       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;
+                       #pragma omp flush(done)
                }
 
-               if (results.empty()) {
+               if (results.empty() && !done) {
                        fprintf(stderr, "%d, Fail. This can't happen?\n",
                                depth);
                        sudoku empty;
-                       return empty;
+                       result = empty;
+                       done = 1;
+                       #pragma omp flush(done)
                }
        }
+       return result;
 }
 
 int sudoku::generate(int min_guesses)

diff --git a/sudoku.h b/sudoku.h
index dee32c5a65258ff8ff7cfa093879fc842251a187..6ba1136d85dbf1ddfaf03e4dc09b8606bff537fa 100644 (file)
--- a/sudoku.h
+++ b/sudoku.h
@@ -35,6 +35,7 @@ private:
        int get_best_guess(int &col, int &row);
        sudoku fill_with_random(int &solvable);
        sudoku remove_randomly(int min_guesses, int depth);
+       sudoku remove_randomly_parallel(int min_guesses, int depth);
        int used_numbers();
 
        char table[9][9];