From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sat, 20 Jun 2009 17:04:51 +0000 (+0300)
Subject: Generator: First version that searches sudokus in parallel threads
X-Git-Url: http://git.itanic.dy.fi/?p=sudoku;a=commitdiff_plain;h=4d428962034d6f89d24436385a968631be3eeaa2

Generator: First version that searches sudokus in parallel threads
---

diff --git a/Makefile b/Makefile
index a5d8c81..0a07af4 100644
--- 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 9279ffd..4d5d288 100644
--- 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 dee32c5..6ba1136 100644
--- 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];