From: Timo Kokkonen Date: Sat, 20 Jun 2009 10:02:23 +0000 (+0300) Subject: generator: Generates now a completely filled sudoku X-Git-Url: http://git.itanic.dy.fi/?p=sudoku;a=commitdiff_plain;h=01e6115104cd36dfb82f715c4a0d4cf878b26783 generator: Generates now a completely filled sudoku --- diff --git a/generator.cpp b/generator.cpp index a578118..81988f2 100644 --- a/generator.cpp +++ b/generator.cpp @@ -2,5 +2,10 @@ int main(int argc, char *argv[]) { + sudoku sudo; + + sudo.generate(0); + sudo.print(); + return 0; } diff --git a/sudoku.cpp b/sudoku.cpp index 3848d6e..a6dd212 100644 --- a/sudoku.cpp +++ b/sudoku.cpp @@ -264,7 +264,7 @@ int sudoku::fill_missing() } } if (verbose) { - std::cout << "Solved " << solved << " numbers\n"; + //std::cout << "Solved " << solved << " numbers\n"; } return solved; @@ -328,11 +328,11 @@ int sudoku::get_best_guess(int &col, int &row) return min; } -sudoku sudoku::solve(int &solvable) +std::vector sudoku::solve_all() { - int x, y, i, ret; + int x, y, i, j, ret; std::string str; - sudoku empty; + std::vector sudokus; // Fill in as much as possible do { @@ -348,20 +348,20 @@ sudoku sudoku::solve(int &solvable) 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); + print(); + return sudokus; } if (verbose) { @@ -372,111 +372,122 @@ sudoku sudoku::solve(int &solvable) // Try guessim something str = get_legal_numbers(x, y); for (i = 0; i < (int)str.length(); i++) { + std::vector 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; + std::cout << "Guesses: " << guesses << std::endl; + + // Return what was solved + return sudokus; } -std::vector 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 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 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; - - //Did it solve? - if (!results.empty()) { -/* printf("Got %d solutions, guessed %d: %s\n", - (int)results.size(), (int)str.size(), - str.c_str());*/ + int can_solve; + guess = guess.fill_with_random(can_solve); - for(j = 0;j < (int)results.size(); j++) { - sudokus.push_back(results.at(j)); - guesses += results.at(j).guesses; - } + //Did it solve? + if (can_solve) { + solvable = 1; + return guess; } - } - std::cout << "Guesses: " << guesses << std::endl; + str.erase(i,1); + } - // Return what was solved - return sudokus; + // It didn't solve + solvable = 0; + return empty; } -void sudoku::generate(int min_guesses) +int sudoku::generate(int min_guesses) { + int solvable; + sudoku tmp = fill_with_random(solvable); + + if (solvable) + *this = tmp; + return solvable; } diff --git a/sudoku.h b/sudoku.h index a0b8971..5028634 100644 --- a/sudoku.h +++ b/sudoku.h @@ -20,9 +20,8 @@ public: int str_to_row(const int row, const std::string &str); std::string get_legal_numbers(const int col, const int row); - sudoku solve(int &solvable); std::vector solve_all(void); - void generate(int min_guesses); + int generate(int min_guesses); int recursion_depth; int guesses; @@ -31,9 +30,10 @@ private: std::string get_row_contents(const int row); std::string get_col_contents(const int col); std::string get_block_contents(const int col, const int row); - int fill_missing(); + int fill_missing(void); void clone_to(sudoku &to); int get_best_guess(int &col, int &row); + sudoku fill_with_random(int &solvable); char table[9][9]; };