From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sat, 20 Jun 2009 15:04:51 +0000 (+0300)
Subject: Generates sudokus at desired difficulty level
X-Git-Url: http://git.itanic.dy.fi/?p=sudoku;a=commitdiff_plain;h=6b3d9a58c639782c132a68d169bc72eed1b5f7aa

Generates sudokus at desired difficulty level
---

diff --git a/generator.cpp b/generator.cpp
index 81988f2..8759582 100644
--- a/generator.cpp
+++ b/generator.cpp
@@ -1,10 +1,28 @@
+#include <stdlib.h>
+
 #include "sudoku.h"
 
 int main(int argc, char *argv[])
 {
 	sudoku sudo;
+	int min_guesses;
+
+	if (argc < 2) {
+		printf("Too few arguments given\n");
+		return -1;
+	}
+
+	min_guesses = atoi(argv[1]);
+	if (min_guesses < 1) {
+		printf("Not a valid number: %s\n", argv[1]);
+		return -2;
+	}
+
+	verbose = 0;
+
+	sudo.generate(min_guesses);
 
-	sudo.generate(0);
+	printf("Got sudoku with %d guesses\n", sudo.guesses);
 	sudo.print();
 
 	return 0;
diff --git a/sudoku.cpp b/sudoku.cpp
index a6dd212..9279ffd 100644
--- 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;
 }
diff --git a/sudoku.h b/sudoku.h
index 5028634..dee32c5 100644
--- a/sudoku.h
+++ b/sudoku.h
@@ -34,6 +34,8 @@ private:
 	void clone_to(sudoku &to);
 	int get_best_guess(int &col, int &row);
 	sudoku fill_with_random(int &solvable);
+	sudoku remove_randomly(int min_guesses, int depth);
+	int used_numbers();
 
 	char table[9][9];
 };