generator: Generates now a completely filled sudoku

diff --git a/generator.cpp b/generator.cpp
index a5781185eca53cfb815b71e336582d47d3aa7fdf..81988f286df2c9f60a280b54e36909fb91c9e816 100644 (file)
--- a/generator.cpp
+++ b/generator.cpp
@@ -2,5 +2,10 @@
 
 int main(int argc, char *argv[])
 {
 
 int main(int argc, char *argv[])
 {

+       sudoku sudo;
+
+       sudo.generate(0);
+       sudo.print();
+

        return 0;
 }
        return 0;
 }

diff --git a/sudoku.cpp b/sudoku.cpp
index 3848d6ec1d0276ad26965f4f48876a3ea95e63dd..a6dd2121a9c13876b9394b6c0934c46fa65e2cff 100644 (file)
--- a/sudoku.cpp
+++ b/sudoku.cpp
@@ -264,7 +264,7 @@ int sudoku::fill_missing()
                        }
                }
        if (verbose) {
                        }
                }
        if (verbose) {

-               std::cout << "Solved " << solved << " numbers\n";
+               //std::cout << "Solved " << solved << " numbers\n";

        }
 
        return solved;
        }
 
        return solved;


@@ -328,11 +328,11 @@ int sudoku::get_best_guess(int &col, int &row)
        return min;
 }
 
        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;
        std::string str;

-       sudoku empty;
+       std::vector<sudoku> sudokus;

 
        // Fill in as much as possible
        do {
 
        // Fill in as much as possible
        do {


@@ -348,20 +348,20 @@ sudoku sudoku::solve(int &solvable)
        switch (ret) {
        case -1:
                // Unsolvable
        switch (ret) {
        case -1:
                // Unsolvable

-               solvable = 0;

                if (verbose) {
                        std::cout << "This is unsolvable, recursion: " 
                                  << recursion_depth << std::endl;
                }
                if (verbose) {
                        std::cout << "This is unsolvable, recursion: " 
                                  << recursion_depth << std::endl;
                }

-               return empty;
+               return sudokus;

        case 0:
                // Solved
        case 0:
                // Solved

-               solvable = 1;

                if (verbose) {
                        std::cout << "Solution found , recursion: " 
                                  << recursion_depth << std::endl;
                }
                if (verbose) {
                        std::cout << "Solution found , recursion: " 
                                  << recursion_depth << std::endl;
                }

-               return *this;
+               sudokus.push_back(*this);
+               print();
+               return sudokus;

        }
 
        if (verbose) {
        }
 
        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++) {
        // Try guessim something
        str = get_legal_numbers(x, y);
        for (i = 0; i < (int)str.length(); i++) {

+               std::vector<sudoku> results;

 
                sudoku guess = *this;
 
                sudoku guess = *this;

-               guess.set(x, y, str[i]);
+               guesses++;

 
                if (verbose) {
                        std::cout << "Guessing number " << str[i] << " to "
                                  << x << "." << y << std::endl;
                }
 
                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.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?
                
                //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> 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::string str;

-       std::vector<sudoku> sudokus;
+       sudoku empty;

 
        // Fill in as much as possible
        do {
                if (verbose) {
 
        // 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);
 
                }
        } 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
        switch (ret) {
        case -1:
                // Unsolvable

+               solvable = 0;

                if (verbose) {
                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
        case 0:
                // Solved

+               solvable = 1;

                if (verbose) {
                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) {
        }
 
        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);
        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;
 
                sudoku guess = *this;

-               guesses++;
+               guess.set(x, y, str[i]);

 
                if (verbose) {
 
                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.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 a0b8971f4fe077babc1db2454220f50231752095..5028634573e2c9baeed23487551e74e796af41de 100644 (file)
--- 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);
        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<sudoku> solve_all(void);
        std::vector<sudoku> solve_all(void);

-       void generate(int min_guesses);
+       int generate(int min_guesses);

 
        int recursion_depth;
        int 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);
        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);
        void clone_to(sudoku &to);
        int get_best_guess(int &col, int &row);

+       sudoku fill_with_random(int &solvable);

 
        char table[9][9];
 };
 
        char table[9][9];
 };