00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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 }