16 for (y = 0; y < 9; y++)
17 for (x = 0; x < 9; x++)
28 static int check_validity(const int col, const int row)
30 if (col < 0 || col >= 9) {
31 DPRINT << "Invalid column: " << col << std::endl;
35 if (row < 0 || row >= 9) {
36 DPRINT << "Invalid row: " << row << std::endl;
42 char sudoku::get(const int col, const int row)
44 if (!check_validity(row, col)) {
45 DPRINT << "over here\n";
49 return table[col][row];
52 int sudoku::set(const int col, const int row, const char val)
56 if (!check_validity(col, row)) {
57 DPRINT << "over here\n";
61 if (table[col][row] != EMPTY) {
62 DPRINT << "Assigning value to a non-empty slot\n";
66 str = get_col_contents(col);
67 if (str.find(val, 0) != std::string::npos) {
68 DPRINT << "Illegal assignment " << col << "." << row << ": "
73 str = get_row_contents(row);
74 if (str.find(val, 0) != std::string::npos) {
75 DPRINT << "Illegal assignment " << col << "." << row << ": "
80 str = get_block_contents(col, row);
81 if (str.find(val, 0) != std::string::npos) {
82 DPRINT << "Illegal assignment " << col << "." << row << ": "
87 table[col][row] = val;
92 int sudoku::str_to_row(const int row, const std::string &str)
94 unsigned int i, col = 0;
97 if (row < 0 || row >= 9) {
98 DPRINT << "Illegal row " << row << std::endl;
102 for (i = 0; i < str.length(); i++) {
112 /* Ignore non-numbers */
113 if (chr < '1' || chr > '9')
116 set(col++, row, chr);
123 void sudoku::print(void)
127 printf("+-------+------+--------+\n");
128 for (y = 0; y < 9; y++) {
130 for (x = 0; x < 9; x++) {
131 printf("%c ", table[x][y]);
137 printf("+-------+-------+-------+\n");
141 void sudoku::print_compact(void)
147 for (y = 0; y < 9; y++)
148 for (x = 0; x < 9; x++, i++)
149 str[i] = table[x][y] != EMPTY ? table[x][y] : '.';
154 void sudoku::clone_to(sudoku &to)
159 for (x = 0; x < 9; x++)
160 for (y = 0; y < 9; y++)
161 to.table[x][y] = table[x][y];
164 std::string sudoku::get_row_contents(int row)
169 for (col = 0; col < 9; col++) {
170 if (table[col][row] != EMPTY)
171 s += table[col][row];
177 std::string sudoku::get_col_contents(int col)
182 for (row = 0; row < 9; row++) {
183 if (table[col][row] != EMPTY)
184 s += table[col][row];
190 std::string sudoku::get_block_contents(int col, int row)
196 if (col < 0 || col >= 9)
197 DPRINT "Aiee " << col << std::endl;
198 if (row < 0 || row >= 9)
199 DPRINT "Aiee " << row << std::endl;
201 col = (col /= 3) * 3;
202 row = (row /= 3) * 3;
204 for (y = 0; y < 3; y++)
205 for (x = 0; x < 3; x++) {
206 c = get(x + col, y + row);
214 static std::string exclude_common(std::string s1, std::string s2)
216 std::string::iterator a, b;
219 for (a = s1.begin(); a != s1.end(); a++) {
220 for (b = s2.begin(); b != s2.end(); b++) {
231 std::string sudoku::get_legal_numbers(int col, int row)
234 std::string a, b, c, ret;
236 if (!check_validity(col, row)) {
237 DPRINT << "over here\n";
246 // std::cout << "[" << col << "." << row << "] ";
248 a = get_col_contents(col);
249 // std::cout << " col " << a;
251 b = get_row_contents(row);
252 // std::cout << " row " << b;
254 c = get_block_contents(col, row);
255 // std::cout << " block " << c;
257 ret = exclude_common("123456789", a);
258 ret = exclude_common(ret, b);
259 ret = exclude_common(ret, c);
261 // std::cout << " legal " << ret << std::endl;
265 int sudoku::fill_missing()
267 int x, y, solved = 0;
270 for (y = 0; y < 9; y++)
271 for (x = 0; x < 9; x++) {
272 num = get_legal_numbers(x, y);
273 if ((num != "0") && (num.length() == 1)) {
279 //std::cout << "Solved " << solved << " numbers\n";
285 int sudoku::get_best_guess(int &col, int &row)
288 int min = 0, filled = 0, illegals = 0;
292 * Initialize row and col with illegal values to spot possible
298 for (y = 0; (y < 9) && !illegals; y++)
299 for (x = 0; x < 9; x++) {
300 numbers = get_legal_numbers(x, y);
302 if (numbers == "0") {
307 if (numbers.length() == 0) {
313 min = numbers.length();
319 if ((int)numbers.length() < min) {
320 min = numbers.length();
326 // std::cout << x << "." << y << ": " << " min "
327 // << numbers << col << "." << row << std::endl;
330 if ((!min && !filled) || illegals) {
331 // DPRINT << "Is this sudoku has no solutions?\n";
335 if (!min && (filled == 99)) {
336 DPRINT << "This sudoku is solved\n";
343 std::vector<sudoku> sudoku::solve_all()
347 std::vector<sudoku> sudokus;
349 // Fill in as much as possible
352 std::cout << std::endl;
355 } while (fill_missing() != 0);
357 ret = get_best_guess(x, y);
359 // Did we solve it yet?
364 std::cout << "This is unsolvable, recursion: "
365 << recursion_depth << std::endl;
371 std::cout << "Solution found , recursion: "
372 << recursion_depth << std::endl;
374 sudokus.push_back(*this);
381 std::cout << "Not solved yet, guessing at depth "
382 << recursion_depth << std::endl;
385 // Try guessim something
386 str = get_legal_numbers(x, y);
387 for (i = 0; i < (int)str.length(); i++) {
388 std::vector<sudoku> results;
390 sudoku guess = *this;
394 std::cout << "Guessing number " << str[i] << " to "
395 << x << "." << y << std::endl;
398 guess.set(x, y, str[i]);
399 guess.recursion_depth = recursion_depth + 1;
402 results = guess.solve_all();
403 guesses += guess.guesses;
406 if (!results.empty()) {
407 /* printf("Got %d solutions, guessed %d: %s\n",
408 (int)results.size(), (int)str.size(),
411 for(j = 0;j < (int)results.size(); j++) {
412 sudokus.push_back(results.at(j));
413 guesses += results.at(j).guesses;
419 std::cout << "Guesses: " << guesses << std::endl;
421 // Return what was solved
425 sudoku sudoku::fill_with_random(int &solvable)
431 // Fill in as much as possible
434 //std::cout << std::endl;
437 } while (fill_missing() != 0);
439 ret = get_best_guess(x, y);
441 // Did we fill it yet?
447 //std::cout << "This is unsolvable, recursion: "
448 // << recursion_depth << std::endl;
455 //std::cout << "Solution found , recursion: "
456 // << recursion_depth << std::endl;
462 //std::cout << "Not solved yet, guessing at depth "
463 // << recursion_depth << std::endl;
466 // Try filling with something
467 str = get_legal_numbers(x, y);
468 while (str.length()) {
469 i = get_random() % str.length();
471 sudoku guess = *this;
472 guess.set(x, y, str[i]);
475 //std::cout << "Trying number " << str[i] << " to "
476 // << x << "." << y << std::endl;
479 guess.recursion_depth = recursion_depth + 1;
482 guess = guess.fill_with_random(can_solve);
498 int sudoku::used_numbers()
501 for (x = 0; x < 9; x++)
502 for (y = 0; y < 9; y++)
503 if (table[x][y] != EMPTY)
510 sudoku sudoku::remove_randomly(int min_guesses, int depth)
512 int count = used_numbers();
516 #pragma omp parallel for firstprivate(stop)
517 for (int i = 0; i < count; i++) {
519 sudoku tmp = *this, tmp2;
520 std::vector<sudoku> results;
525 /* remove a number */
527 x = get_random() % 9;
528 y = get_random() % 9;
529 } while(tmp.get(x,y) == EMPTY);
530 tmp.table[x][y] = EMPTY;
532 //printf("Got now:\n");
537 results = tmp.solve_all();
539 /* Does it still have only one solution */
540 if (results.size() == 1 && !done) {
541 /* but not hard enough yet? */
542 if (tmp.guesses >= min_guesses) {
544 printf("%d, Good!\n", depth);
547 #pragma omp flush(done)
549 printf("%2d, got only %3d guesses ", depth,
556 tmp2 = tmp.remove_randomly(min_guesses,
559 /* test for emptiness */
560 if (tmp2.guesses == 0) {
564 if (tmp2.guesses >= min_guesses) {
567 #pragma omp flush(done)
569 printf("%d: Guesses: %d, "
571 depth, tmp2.guesses);
577 if ((results.size() > 1) && !done) {
578 /* oops, removed too many */
580 //printf("%d, Got multiple results\n", depth);
585 if (results.empty() && !done) {
586 fprintf(stderr, "%d, Fail. This can't happen?\n",
595 int sudoku::generate(int min_guesses)
598 sudoku tmp = fill_with_random(solvable);
603 /* Right, we got it filled */
604 tmp = tmp.remove_randomly(min_guesses, 0);