return -1;
}
-
table[col][row] = val;
return 0;
void sudoku::print(void)
{
- int x,y;
+ int x, y;
printf("+-------+------+--------+\n");
for (y = 0; y < 9; y++) {
}
}
-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)
}
}
if (verbose) {
- std::cout << "Solved " << solved << " numbers\n";
+ //std::cout << "Solved " << solved << " numbers\n";
}
return solved;
return min;
}
-sudoku sudoku::solve(int &solvable)
+std::vector<sudoku> sudoku::solve_all()
{
- int x, y, i, ret;
+ int x, y, i, j, ret;
std::string str;
- sudoku empty;
+ std::vector<sudoku> sudokus;
// Fill in as much as possible
do {
switch (ret) {
case -1:
// Unsolvable
- solvable = 0;
if (verbose) {
std::cout << "This is unsolvable, recursion: "
<< recursion_depth << std::endl;
}
- return empty;
+ return sudokus;
case 0:
// Solved
- solvable = 1;
if (verbose) {
std::cout << "Solution found , recursion: "
<< recursion_depth << std::endl;
}
- return *this;
+ sudokus.push_back(*this);
+ if (verbose)
+ print();
+ return sudokus;
}
if (verbose) {
// Try guessim something
str = get_legal_numbers(x, y);
for (i = 0; i < (int)str.length(); i++) {
+ std::vector<sudoku> results;
sudoku guess = *this;
- guess.set(x, y, str[i]);
+ guesses++;
if (verbose) {
std::cout << "Guessing number " << str[i] << " to "
<< x << "." << y << std::endl;
}
-
+
+ guess.set(x, y, str[i]);
guess.recursion_depth = recursion_depth + 1;
+ guess.guesses = 0;
- int can_solve;
- guess = guess.solve(can_solve);
+ results = guess.solve_all();
+ guesses += guess.guesses;
//Did it solve?
- if (can_solve)
- return guess;
+ if (!results.empty()) {
+/* printf("Got %d solutions, guessed %d: %s\n",
+ (int)results.size(), (int)str.size(),
+ str.c_str());*/
+
+ for(j = 0;j < (int)results.size(); j++) {
+ sudokus.push_back(results.at(j));
+ guesses += results.at(j).guesses;
+ }
+ }
}
- // It didn't solve
- solvable = 0;
- return empty;
+ if (verbose)
+ std::cout << "Guesses: " << guesses << std::endl;
+
+ // Return what was solved
+ return sudokus;
}
-std::vector<sudoku> sudoku::solve_all()
+sudoku sudoku::fill_with_random(int &solvable)
{
- int x, y, i, j, ret;
+ int x, y, i, ret;
std::string str;
- std::vector<sudoku> sudokus;
+ sudoku empty;
// Fill in as much as possible
do {
if (verbose) {
- std::cout << std::endl;
- print();
+ //std::cout << std::endl;
+ //print();
}
} while (fill_missing() != 0);
ret = get_best_guess(x, y);
- // Did we solve it yet?
+ // Did we fill it yet?
switch (ret) {
case -1:
// Unsolvable
+ solvable = 0;
if (verbose) {
- std::cout << "This is unsolvable, recursion: "
- << recursion_depth << std::endl;
+ //std::cout << "This is unsolvable, recursion: "
+ // << recursion_depth << std::endl;
}
- return sudokus;
+ return empty;
case 0:
// Solved
+ solvable = 1;
if (verbose) {
- std::cout << "Solution found , recursion: "
- << recursion_depth << std::endl;
+ //std::cout << "Solution found , recursion: "
+ // << recursion_depth << std::endl;
}
- sudokus.push_back(*this);
- print();
- return sudokus;
+ return *this;
}
if (verbose) {
- std::cout << "Not solved yet, guessing at depth "
- << recursion_depth << std::endl;
+ //std::cout << "Not solved yet, guessing at depth "
+ // << recursion_depth << std::endl;
}
- // Try guessim something
+ // Try filling with something
str = get_legal_numbers(x, y);
- for (i = 0; i < (int)str.length(); i++) {
- std::vector<sudoku> results;
+ while (str.length()) {
+ i = get_random() % str.length();
sudoku guess = *this;
- guesses++;
+ guess.set(x, y, str[i]);
if (verbose) {
- std::cout << "Guessing number " << str[i] << " to "
- << x << "." << y << std::endl;
+ //std::cout << "Trying number " << str[i] << " to "
+ // << x << "." << y << std::endl;
}
- guess.set(x, y, str[i]);
guess.recursion_depth = recursion_depth + 1;
- guess.guesses = 0;
- results = guess.solve_all();
- guesses += guess.guesses;
-
+ int can_solve;
+ guess = guess.fill_with_random(can_solve);
+
//Did it solve?
- if (!results.empty()) {
-/* printf("Got %d solutions, guessed %d: %s\n",
- (int)results.size(), (int)str.size(),
- str.c_str());*/
+ if (can_solve) {
+ solvable = 1;
+ return guess;
+ }
- for(j = 0;j < (int)results.size(); j++) {
- sudokus.push_back(results.at(j));
- guesses += results.at(j).guesses;
+ str.erase(i,1);
+ }
+
+ // It didn't solve
+ solvable = 0;
+ 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;
}
}
- }
- std::cout << "Guesses: " << guesses << std::endl;
+ if ((results.size() > 1) && !done) {
+ /* oops, removed too many */
+ sudoku empty;
+ //printf("%d, Got multiple results\n", depth);
+ result = empty;
+ stop = 1;
+ }
- // Return what was solved
- return sudokus;
+ if (results.empty() && !done) {
+ fprintf(stderr, "%d, Fail. This can't happen?\n",
+ depth);
+ sudoku empty;
+ result = empty;
+ }
+ }
+ return result;
}
-void sudoku::generate(int min_guesses)
+int sudoku::generate(int min_guesses)
{
+ int solvable;
+ sudoku tmp = fill_with_random(solvable);
+
+ if (!solvable)
+ return -1;
+
+ /* Right, we got it filled */
+ tmp = tmp.remove_randomly(min_guesses, 0);
+
+ *this = tmp;
+ return solvable;
}
projects / sudoku / blobdiff