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 std::string sudoku::get_row_contents(int row)
159 for (col = 0; col < 9; col++) {
160 if (table[col][row] != EMPTY)
161 s += table[col][row];
167 std::string sudoku::get_col_contents(int col)
172 for (row = 0; row < 9; row++) {
173 if (table[col][row] != EMPTY)
174 s += table[col][row];
180 std::string sudoku::get_block_contents(int col, int row)
186 if (col < 0 || col >= 9)
187 DPRINT "Aiee " << col << std::endl;
188 if (row < 0 || row >= 9)
189 DPRINT "Aiee " << row << std::endl;
191 col = (col /= 3) * 3;
192 row = (row /= 3) * 3;
194 for (y = 0; y < 3; y++)
195 for (x = 0; x < 3; x++) {
196 c = get(x + col, y + row);
204 static std::string exclude_common(std::string s1, std::string s2)
206 std::string::iterator a, b;
209 for (a = s1.begin(); a != s1.end(); a++) {
210 for (b = s2.begin(); b != s2.end(); b++) {
221 std::string sudoku::get_legal_numbers(int col, int row)
224 std::string a, b, c, ret;
226 if (!check_validity(col, row)) {
227 DPRINT << "over here\n";
236 // std::cout << "[" << col << "." << row << "] ";
238 a = get_col_contents(col);
239 // std::cout << " col " << a;
241 b = get_row_contents(row);
242 // std::cout << " row " << b;
244 c = get_block_contents(col, row);
245 // std::cout << " block " << c;
247 ret = exclude_common("123456789", a);
248 ret = exclude_common(ret, b);
249 ret = exclude_common(ret, c);
251 // std::cout << " legal " << ret << std::endl;
255 int sudoku::fill_missing()
257 int x, y, solved = 0;
260 for (y = 0; y < 9; y++)
261 for (x = 0; x < 9; x++) {
262 num = get_legal_numbers(x, y);
263 if ((num != "0") && (num.length() == 1)) {
269 //std::cout << "Solved " << solved << " numbers\n";
275 int sudoku::get_best_guess(int &col, int &row)
278 int min = 0, filled = 0, illegals = 0;
282 * Initialize row and col with illegal values to spot possible
288 for (y = 0; (y < 9) && !illegals; y++)
289 for (x = 0; x < 9; x++) {
290 numbers = get_legal_numbers(x, y);
292 if (numbers == "0") {
297 if (numbers.length() == 0) {
303 min = numbers.length();
309 if ((int)numbers.length() < min) {
310 min = numbers.length();
316 // std::cout << x << "." << y << ": " << " min "
317 // << numbers << col << "." << row << std::endl;
320 if ((!min && !filled) || illegals) {
321 // DPRINT << "Is this sudoku has no solutions?\n";
325 if (!min && (filled == 99)) {
326 DPRINT << "This sudoku is solved\n";
333 std::vector<sudoku> sudoku::solve_all()
337 std::vector<sudoku> sudokus;
339 // Fill in as much as possible
342 std::cout << std::endl;
345 } while (fill_missing() != 0);
347 ret = get_best_guess(x, y);
349 // Did we solve it yet?
354 std::cout << "This is unsolvable, recursion: "
355 << recursion_depth << std::endl;
361 std::cout << "Solution found , recursion: "
362 << recursion_depth << std::endl;
364 sudokus.push_back(*this);
371 std::cout << "Not solved yet, guessing at depth "
372 << recursion_depth << std::endl;
375 // Try guessim something
376 str = get_legal_numbers(x, y);
377 for (i = 0; i < (int)str.length(); i++) {
378 std::vector<sudoku> results;
380 sudoku guess = *this;
384 std::cout << "Guessing number " << str[i] << " to "
385 << x << "." << y << std::endl;
388 guess.set(x, y, str[i]);
389 guess.recursion_depth = recursion_depth + 1;
392 results = guess.solve_all();
393 guesses += guess.guesses;
396 if (!results.empty()) {
397 /* printf("Got %d solutions, guessed %d: %s\n",
398 (int)results.size(), (int)str.size(),
401 for(j = 0;j < (int)results.size(); j++) {
402 sudokus.push_back(results.at(j));
403 guesses += results.at(j).guesses;
409 std::cout << "Guesses: " << guesses << std::endl;
411 // Return what was solved
415 sudoku sudoku::fill_with_random(int &solvable)
421 // Fill in as much as possible
424 //std::cout << std::endl;
427 } while (fill_missing() != 0);
429 ret = get_best_guess(x, y);
431 // Did we fill it yet?
437 //std::cout << "This is unsolvable, recursion: "
438 // << recursion_depth << std::endl;
445 //std::cout << "Solution found , recursion: "
446 // << recursion_depth << std::endl;
452 //std::cout << "Not solved yet, guessing at depth "
453 // << recursion_depth << std::endl;
456 // Try filling with something
457 str = get_legal_numbers(x, y);
458 while (str.length()) {
459 i = get_random() % str.length();
461 sudoku guess = *this;
462 guess.set(x, y, str[i]);
465 //std::cout << "Trying number " << str[i] << " to "
466 // << x << "." << y << std::endl;
469 guess.recursion_depth = recursion_depth + 1;
472 guess = guess.fill_with_random(can_solve);
488 int sudoku::used_numbers()
491 for (x = 0; x < 9; x++)
492 for (y = 0; y < 9; y++)
493 if (table[x][y] != EMPTY)
500 sudoku sudoku::remove_randomly(int min_guesses, int depth)
502 int count = used_numbers();
506 #pragma omp parallel for firstprivate(stop)
507 for (int i = 0; i < count; i++) {
509 sudoku tmp = *this, tmp2;
510 std::vector<sudoku> results;
515 /* remove a number */
517 x = get_random() % 9;
518 y = get_random() % 9;
519 } while(tmp.get(x,y) == EMPTY);
520 tmp.table[x][y] = EMPTY;
522 //printf("Got now:\n");
527 results = tmp.solve_all();
529 /* Does it still have only one solution */
530 if (results.size() == 1 && !done) {
531 /* but not hard enough yet? */
532 if (tmp.guesses >= min_guesses) {
534 printf("%d, Good!\n", depth);
537 #pragma omp flush(done)
539 printf("%2d, got only %3d guesses ", depth,
546 tmp2 = tmp.remove_randomly(min_guesses,
549 /* test for emptiness */
550 if (tmp2.guesses == 0) {
554 if (tmp2.guesses >= min_guesses) {
557 #pragma omp flush(done)
559 printf("%d: Guesses: %d, "
561 depth, tmp2.guesses);
567 if ((results.size() > 1) && !done) {
568 /* oops, removed too many */
570 //printf("%d, Got multiple results\n", depth);
575 if (results.empty() && !done) {
576 fprintf(stderr, "%d, Fail. This can't happen?\n",
585 int sudoku::generate(int min_guesses)
588 sudoku tmp = fill_with_random(solvable);
593 /* Right, we got it filled */
594 tmp = tmp.remove_randomly(min_guesses, 0);