sudoku_generator.cpp

Go to the documentation of this file.
00001 /*
00002  * Sudoku: A plug-in for the Video Disk Recorder
00003  *
00004  * Copyright (C) 2005-2010, Thomas Günther <tom@toms-cafe.de>
00005  *
00006  * This program is free software; you can redistribute it and/or modify
00007  * it under the terms of the GNU General Public License as published by
00008  * the Free Software Foundation; either version 2 of the License, or
00009  * (at your option) any later version.
00010  *
00011  * This program is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  * GNU General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License along
00017  * with this program; if not, write to the Free Software Foundation, Inc.,
00018  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00019  */
00020 
00021 #include "../puzzle.h"
00022 #include "../solver.h"
00023 #include "../generator.h"
00024 #include <stdio.h>
00025 #include <string.h>
00026 #include <getopt.h>
00027 
00028 using namespace Sudoku;
00029 
00030 
00031 int print_version()
00032 {
00033   printf("sudoku_generator %s\n"
00034          "Copyright (C) 2005-2010, Thomas Günther <tom@toms-cafe.de>\n"
00035          "This GPL program comes with ABSOLUTELY NO WARRANTY;\n"
00036          "this is free software, and you are welcome to redistribute it\n"
00037          "under certain conditions; see the source for details.\n", VERSION);
00038   return 0;
00039 }
00040 
00041 void print_description(unsigned int givens_count)
00042 {
00043   printf("Sudoku with %d givens generated by sudoku_generator %s\n"
00044          "    This puzzle can be used without any limitations.\n"
00045          "\n", givens_count, VERSION);
00046 }
00047 
00048 int print_usage()
00049 {
00050   printf("Usage: sudoku_generator [-n|--non-sym] [-d|--dump] [<givens_count>]\n"
00051          "         Generate a Sudoku puzzle.\n"
00052          "           givens_count   Number of givens (<= 81). Default is 36.\n"
00053          "                          Less than 26 givens takes very long.\n"
00054          "           -n, --non-sym  Generate a non-symmetric Sudoku puzzle.\n"
00055          "           -d, --dump     Dump the generated Sudoku (don't print).\n"
00056          "\n"
00057          "       sudoku_generator -s|--solve <sudoku_dump>\n"
00058          "         Solve a Sudoku puzzle.\n"
00059          "           sudoku_dump    String with 81 * 1-9 or _ (+ ignored).\n"
00060          "\n"
00061          "       sudoku_generator -p|--print <sudoku_dump>\n"
00062          "         Print a Sudoku puzzle.\n"
00063          "           sudoku_dump    String with 81 * 1-9 or _ (+ ignored).\n"
00064          "\n"
00065 #ifdef WITH_TEST
00066          "       sudoku_generator -t|--test\n"
00067          "         Perform some test procedures.\n"
00068          "\n"
00069 #endif
00070          "       sudoku_generator -v|--version\n"
00071          "         Print version information and exit.\n"
00072          "\n"
00073          "       sudoku_generator -h|--help\n"
00074          "         Print this help message and exit.\n"
00075          "\n");
00076   return 2;
00077 }
00078 
00079 void print_sudoku(const Numbers* sudoku_list[], unsigned int count,
00080                   unsigned int givens_count = 0)
00081 {
00082   printf("\n");
00083   for (unsigned int row = 0; row <= DIM; ++row)
00084   {
00085     if (row % RDIM == 0)
00086     {
00087       for (unsigned int idx = 0; idx < count; ++idx)
00088       {
00089         printf("              ");
00090         for (unsigned int col = 0; col < DIM; ++col)
00091         {
00092           if (col % RDIM == 0)
00093             printf("  ");
00094           printf("- ");
00095         }
00096         printf("  ");
00097       }
00098       printf("\n");
00099     }
00100     if (row < DIM)
00101     {
00102       for (unsigned int idx = 0; idx < count; ++idx)
00103       {
00104         printf("              ");
00105         for (unsigned int col = 0; col < DIM; ++col)
00106         {
00107           if (col % RDIM == 0)
00108             printf("| ");
00109           unsigned int n = sudoku_list[idx]->get(Pos(col, row));
00110           if (n)
00111             printf("%d ", n);
00112           else
00113             printf("  ");
00114         }
00115         printf("| ");
00116       }
00117       printf("\n");
00118     }
00119   }
00120   printf("\n");
00121   if (givens_count != 0)
00122     print_description(givens_count);
00123 }
00124 
00125 void print_sudoku(const Numbers& sudoku, unsigned int givens_count = 0)
00126 {
00127   const Numbers* sudoku_list[] = { &sudoku };
00128   print_sudoku(sudoku_list, 1, givens_count);
00129 }
00130 
00131 void print_sudoku(const Numbers& sudoku1, const Numbers& sudoku2,
00132                   unsigned int givens_count = 0)
00133 {
00134   const Numbers* sudoku_list[] = { &sudoku1, &sudoku2 };
00135   print_sudoku(sudoku_list, 2, givens_count);
00136 }
00137 
00138 void dump_sudoku(const Numbers& sudoku)
00139 {
00140   printf("%s\n", sudoku.get_dump());
00141 }
00142 
00143 int generate_puzzle(unsigned int givens_count, bool non_sym, bool dump)
00144 {
00145   Puzzle puzzle;
00146   Generator generator(puzzle, givens_count, !non_sym);
00147   generator.find_next_solution();
00148   if (!generator.solution_is_valid())
00149     return 1;
00150   if (dump)
00151     dump_sudoku(puzzle);
00152   else
00153     print_sudoku(puzzle, givens_count);
00154   return 0;
00155 }
00156 
00157 int solve_puzzle(const char *dump)
00158 {
00159   Numbers numbers(dump);
00160   bool given_marks[SDIM];
00161   for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
00162     given_marks[p] = numbers.get(p) != 0;
00163   Puzzle puzzle;
00164   puzzle.set_givens(numbers, given_marks);
00165   Solver solver(puzzle);
00166   solver.find_next_solution();
00167   if (!solver.solution_is_valid())
00168     return 1;
00169   print_sudoku(numbers, puzzle);
00170   solver.find_next_solution();
00171   if (!solver.solution_is_valid())
00172     return 0;
00173   printf("Error: Sudoku has more than one solution!\n");
00174   return 1;
00175 }
00176 
00177 int print_puzzle(const char *dump)
00178 {
00179   Numbers numbers(dump);
00180   print_sudoku(numbers);
00181   return 0;
00182 }
00183 
00184 #ifdef WITH_TEST
00185 bool test_search_first()
00186 {
00187   bool correct = true;
00188   printf("Search the first Sudoku!\n");
00189   Puzzle puzzle;
00190   Solver solver(puzzle);
00191   solver.find_next_solution();
00192   if (solver.solution_is_valid())
00193     print_sudoku(puzzle);
00194   else
00195     correct = false, printf("Error: Sudoku is invalid!\n");
00196   printf("Search the second Sudoku!\n");
00197   solver.find_next_solution();
00198   if (solver.solution_is_valid())
00199     print_sudoku(puzzle);
00200   else
00201     correct = false, printf("Error: Sudoku is invalid!\n");
00202   return correct;
00203 }
00204 
00205 bool test_search_random()
00206 {
00207   bool correct = true;
00208   printf("Search a random Sudoku!\n");
00209   Puzzle puzzle;
00210   Solver solver(puzzle, true);
00211   solver.find_next_solution();
00212   if (solver.solution_is_valid())
00213     print_sudoku(puzzle);
00214   else
00215     correct = false, printf("Error: Sudoku is invalid!\n");
00216   printf("Search another random Sudoku!\n");
00217   solver.reset();
00218   solver.find_next_solution();
00219   if (solver.solution_is_valid())
00220     print_sudoku(puzzle);
00221   else
00222     correct = false, printf("Error: Sudoku is invalid!\n");
00223   return correct;
00224 }
00225 
00226 bool test_generate_symmetric()
00227 {
00228   bool correct = true;
00229   printf("Generate a random Sudoku with 36 symmetric givens!\n");
00230   Puzzle puzzle;
00231   Generator generator(puzzle, 36);
00232   generator.find_next_solution();
00233   if (generator.solution_is_valid())
00234     print_sudoku(puzzle);
00235   else
00236     correct = false, printf("Error: Sudoku is invalid!\n");
00237   printf("Solve the generated Sudoku!\n");
00238   Solver solver(puzzle);
00239   solver.find_next_solution();
00240   if (solver.solution_is_valid())
00241     print_sudoku(puzzle);
00242   else
00243     correct = false, printf("Error: Sudoku is invalid!\n");
00244   solver.find_next_solution();
00245   if (solver.solution_is_valid())
00246     correct = false, print_sudoku(puzzle),
00247       printf("Error: Sudoku has more than one solution!\n");
00248   else
00249     printf("Sudoku has only one solution!\n");
00250   printf("\n");
00251   return correct;
00252 }
00253 
00254 bool test_generate_non_symmetric()
00255 {
00256   bool correct = true;
00257   printf("Generate a random Sudoku with 26 non-symmetric givens!\n");
00258   Puzzle puzzle;
00259   Generator generator(puzzle, 26, false);
00260   generator.find_next_solution();
00261   if (generator.solution_is_valid())
00262     print_sudoku(puzzle);
00263   else
00264     correct = false, printf("Error: Sudoku is invalid!\n");
00265   printf("Solve the generated Sudoku!\n");
00266   Solver solver(puzzle);
00267   solver.find_next_solution();
00268   if (solver.solution_is_valid())
00269     print_sudoku(puzzle);
00270   else
00271     correct = false, printf("Error: Sudoku is invalid!\n");
00272   solver.find_next_solution();
00273   if (solver.solution_is_valid())
00274     correct = false, print_sudoku(puzzle),
00275       printf("Error: Sudoku has more than one solution!\n");
00276   else
00277     printf("Sudoku has only one solution!\n");
00278   printf("\n");
00279   return correct;
00280 }
00281 
00282 int test_sudoku()
00283 {
00284   unsigned int count = 0;
00285   unsigned int error = 0;
00286   ++count;
00287   if (!test_search_first())
00288     ++error;
00289   ++count;
00290   if (!test_search_random())
00291     ++error;
00292   ++count;
00293   if (!test_generate_symmetric())
00294     ++error;
00295   ++count;
00296   if (!test_generate_non_symmetric())
00297     ++error;
00298   if (error > 0)
00299     printf("%d errors in %d tests\n", error, count);
00300   else
00301     printf("All %d tests correct\n", count);
00302   if (error > 0)
00303     return 1;
00304   return 0;
00305 }
00306 #endif // WITH_TEST
00307 
00308 int main(int argc, char* argv[])
00309 {
00310   static const struct option long_options[] =
00311   {
00312     { "non-sym", no_argument, NULL, 'n' },
00313     { "dump",    no_argument, NULL, 'd' },
00314     { "solve",   no_argument, NULL, 's' },
00315     { "print",   no_argument, NULL, 'p' },
00316 #ifdef WITH_TEST
00317     { "test",    no_argument, NULL, 't' },
00318 #endif
00319     { "version", no_argument, NULL, 'v' },
00320     { "help",    no_argument, NULL, 'h' },
00321     { NULL }
00322   };
00323 #ifdef WITH_TEST
00324   static const char* options = "ndsptvh";
00325 #else
00326   static const char* options = "ndspvh";
00327 #endif
00328   bool non_sym = false;
00329   bool dump    = false;
00330   bool solve   = false;
00331   bool print   = false;
00332   bool test    = false;
00333   bool version = false;
00334   bool help    = false;
00335   bool error   = false;
00336   int c;
00337   while ((c = getopt_long(argc, argv, options, long_options, NULL)) != -1)
00338   {
00339     switch (c)
00340     {
00341       case 'n': non_sym = true; break;
00342       case 'd': dump    = true; break;
00343       case 's': solve   = true; break;
00344       case 'p': print   = true; break;
00345 #ifdef WITH_TEST
00346       case 't': test    = true; break;
00347 #endif
00348       case 'v': version = true; break;
00349       case 'h': help    = true; break;
00350       default:  error   = true;
00351     }
00352   }
00353   int arg_count = argc - optind;
00354 
00355   bool generate = non_sym || dump ||
00356                   (arg_count == 0 && !test && !version && !help) ||
00357                   (arg_count == 1 && !solve && !print);
00358   unsigned int givens_count = 36;
00359   if (arg_count == 1 && generate &&
00360       sscanf(argv[optind], "%u", &givens_count) != 1)
00361     return print_usage();
00362 
00363   if ((generate ? 1 : 0) + (solve ? 1 : 0) + (print ? 1 : 0) + (test ? 1 : 0) +
00364       (version ? 1 : 0) + (help ? 1 : 0) > 1 || error)
00365     return print_usage();
00366 
00367   if (generate && 0 < givens_count && givens_count <= SDIM)
00368     return generate_puzzle(givens_count, non_sym, dump);
00369 
00370   if (solve && arg_count == 1 && strlen(argv[optind]) >= SDIM)
00371     return solve_puzzle(argv[optind]);
00372 
00373   if (print && arg_count == 1 && strlen(argv[optind]) >= SDIM)
00374     return print_puzzle(argv[optind]);
00375 
00376 #ifdef WITH_TEST
00377   if (test)
00378     return test_sudoku();
00379 #endif
00380 
00381   if (version)
00382     return print_version();
00383 
00384   return print_usage();
00385 }
Generated on Mon Apr 5 17:01:07 2010 for VDR plugin 'Sudoku' by  doxygen 1.6.3