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 << ": "
88 table[col][row] = val;
93 int sudoku::str_to_row(const int row, const std::string &str)
95 unsigned int i, col = 0;
98 if (row < 0 || row >= 9) {
99 DPRINT << "Illegal row " << row << std::endl;
103 for (i = 0; i < str.length(); i++) {
113 /* Ignore non-numbers */
114 if (chr < '1' || chr > '9')
117 set(col++, row, chr);
124 void sudoku::print(void)
128 printf("+-------+------+--------+\n");
129 for (y = 0; y < 9; y++) {
131 for (x = 0; x < 9; x++) {
132 printf("%c ", table[x][y]);
138 printf("+-------+-------+-------+\n");
142 void sudoku::clone_to(sudoku &to)
147 for (x = 0; x < 9; x++)
148 for (y = 0; y < 9; y++)
149 to.table[x][y] = table[x][y];
152 std::string sudoku::get_row_contents(int row)
157 for (col = 0; col < 9; col++) {
158 if (table[col][row] != EMPTY)
159 s += table[col][row];
165 std::string sudoku::get_col_contents(int col)
170 for (row = 0; row < 9; row++) {
171 if (table[col][row] != EMPTY)
172 s += table[col][row];
178 std::string sudoku::get_block_contents(int col, int row)
184 if (col < 0 || col >= 9)
185 DPRINT "Aiee " << col << std::endl;
186 if (row < 0 || row >= 9)
187 DPRINT "Aiee " << row << std::endl;
189 col = (col /= 3) * 3;
190 row = (row /= 3) * 3;
192 for (y = 0; y < 3; y++)
193 for (x = 0; x < 3; x++) {
194 c = get(x + col, y + row);
202 static std::string exclude_common(std::string s1, std::string s2)
204 std::string::iterator a, b;
207 for (a = s1.begin(); a != s1.end(); a++) {
208 for (b = s2.begin(); b != s2.end(); b++) {
219 std::string sudoku::get_legal_numbers(int col, int row)
222 std::string a, b, c, ret;
224 if (!check_validity(col, row)) {
225 DPRINT << "over here\n";
234 // std::cout << "[" << col << "." << row << "] ";
236 a = get_col_contents(col);
237 // std::cout << " col " << a;
239 b = get_row_contents(row);
240 // std::cout << " row " << b;
242 c = get_block_contents(col, row);
243 // std::cout << " block " << c;
245 ret = exclude_common("123456789", a);
246 ret = exclude_common(ret, b);
247 ret = exclude_common(ret, c);
249 // std::cout << " legal " << ret << std::endl;
253 int sudoku::fill_missing()
255 int x, y, solved = 0;
258 for (y = 0; y < 9; y++)
259 for (x = 0; x < 9; x++) {
260 num = get_legal_numbers(x, y);
261 if ((num != "0") && (num.length() == 1)) {
267 std::cout << "Solved " << solved << " numbers\n";
273 int sudoku::get_best_guess(int &col, int &row)
276 int min = 0, filled = 0, illegals = 0;
280 * Initialize row and col with illegal values to spot possible
286 for (y = 0; (y < 9) && !illegals; y++)
287 for (x = 0; x < 9; x++) {
288 numbers = get_legal_numbers(x, y);
290 if (numbers == "0") {
295 if (numbers.length() == 0) {
301 min = numbers.length();
307 if ((int)numbers.length() < min) {
308 min = numbers.length();
314 // std::cout << x << "." << y << ": " << " min "
315 // << numbers << col << "." << row << std::endl;
318 if ((!min && !filled) || illegals) {
319 // DPRINT << "Is this sudoku has no solutions?\n";
323 if (!min && (filled == 99)) {
324 DPRINT << "This sudoku is solved\n";
331 sudoku sudoku::solve(int &solvable)
337 // Fill in as much as possible
340 std::cout << std::endl;
343 } while (fill_missing() != 0);
345 ret = get_best_guess(x, y);
347 // Did we solve it yet?
353 std::cout << "This is unsolvable, recursion: "
354 << recursion_depth << std::endl;
361 std::cout << "Solution found , recursion: "
362 << recursion_depth << std::endl;
368 std::cout << "Not solved yet, guessing at depth "
369 << recursion_depth << std::endl;
372 // Try guessim something
373 str = get_legal_numbers(x, y);
374 for (i = 0; i < (int)str.length(); i++) {
376 sudoku guess = *this;
377 guess.set(x, y, str[i]);
380 std::cout << "Guessing number " << str[i] << " to "
381 << x << "." << y << std::endl;
384 guess.recursion_depth = recursion_depth + 1;
387 guess = guess.solve(can_solve);
399 std::vector<sudoku> sudoku::solve_all()
403 std::vector<sudoku> sudokus;
405 // Fill in as much as possible
408 std::cout << std::endl;
411 } while (fill_missing() != 0);
413 ret = get_best_guess(x, y);
415 // Did we solve it yet?
420 std::cout << "This is unsolvable, recursion: "
421 << recursion_depth << std::endl;
427 std::cout << "Solution found , recursion: "
428 << recursion_depth << std::endl;
430 sudokus.push_back(*this);
436 std::cout << "Not solved yet, guessing at depth "
437 << recursion_depth << std::endl;
440 // Try guessim something
441 str = get_legal_numbers(x, y);
442 for (i = 0; i < (int)str.length(); i++) {
443 std::vector<sudoku> results;
445 sudoku guess = *this;
449 std::cout << "Guessing number " << str[i] << " to "
450 << x << "." << y << std::endl;
453 guess.set(x, y, str[i]);
454 guess.recursion_depth = recursion_depth + 1;
457 results = guess.solve_all();
458 guesses += guess.guesses;
461 if (!results.empty()) {
462 /* printf("Got %d solutions, guessed %d: %s\n",
463 (int)results.size(), (int)str.size(),
466 for(j = 0;j < (int)results.size(); j++) {
467 sudokus.push_back(results.at(j));
468 guesses += results.at(j).guesses;
473 std::cout << "Guesses: " << guesses << std::endl;
475 // Return what was solved
479 void sudoku::generate(int min_guesses)