15 for (y = 0; y < 9; y++)
16 for (x = 0; x < 9; x++)
27 static int check_validity(const int col, const int row)
29 if (col < 0 || col >= 9) {
30 DPRINT << "Invalid column: " << col << std::endl;
34 if (row < 0 || row >= 9) {
35 DPRINT << "Invalid row: " << row << std::endl;
41 char sudoku::get(const int col, const int row)
43 if (!check_validity(row, col)) {
44 DPRINT << "over here\n";
48 return table[col][row];
51 int sudoku::set(const int col, const int row, const char val)
55 if (!check_validity(col, row)) {
56 DPRINT << "over here\n";
60 if (table[col][row] != EMPTY) {
61 DPRINT << "Assigning value to a non-empty slot\n";
65 str = get_col_contents(col);
66 if (str.find(val, 0) != std::string::npos) {
67 DPRINT << "Illegal assignment " << col << "." << row << ": "
72 str = get_row_contents(row);
73 if (str.find(val, 0) != std::string::npos) {
74 DPRINT << "Illegal assignment " << col << "." << row << ": "
79 str = get_block_contents(col, row);
80 if (str.find(val, 0) != std::string::npos) {
81 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::clone_to(sudoku &to)
146 for (x = 0; x < 9; x++)
147 for (y = 0; y < 9; y++)
148 to.table[x][y] = table[x][y];
151 std::string sudoku::get_row_contents(int row)
156 for (col = 0; col < 9; col++) {
157 if (table[col][row] != EMPTY)
158 s += table[col][row];
164 std::string sudoku::get_col_contents(int col)
169 for (row = 0; row < 9; row++) {
170 if (table[col][row] != EMPTY)
171 s += table[col][row];
177 std::string sudoku::get_block_contents(int col, int row)
183 if (col < 0 || col >= 9)
184 DPRINT "Aiee " << col << std::endl;
185 if (row < 0 || row >= 9)
186 DPRINT "Aiee " << row << std::endl;
188 col = (col /= 3) * 3;
189 row = (row /= 3) * 3;
191 for (y = 0; y < 3; y++)
192 for (x = 0; x < 3; x++) {
193 c = get(x + col, y + row);
201 static std::string exclude_common(std::string s1, std::string s2)
203 std::string::iterator a, b;
206 for (a = s1.begin(); a != s1.end(); a++) {
207 for (b = s2.begin(); b != s2.end(); b++) {
218 std::string sudoku::get_legal_numbers(int col, int row)
221 std::string a, b, c, ret;
223 if (!check_validity(col, row)) {
224 DPRINT << "over here\n";
233 // std::cout << "[" << col << "." << row << "] ";
235 a = get_col_contents(col);
236 // std::cout << " col " << a;
238 b = get_row_contents(row);
239 // std::cout << " row " << b;
241 c = get_block_contents(col, row);
242 // std::cout << " block " << c;
244 ret = exclude_common("123456789", a);
245 ret = exclude_common(ret, b);
246 ret = exclude_common(ret, c);
248 // std::cout << " legal " << ret << std::endl;
252 int sudoku::fill_missing()
254 int x, y, solved = 0;
257 for (y = 0; y < 9; y++)
258 for (x = 0; x < 9; x++) {
259 num = get_legal_numbers(x, y);
260 if ((num != "0") && (num.length() == 1)) {
266 std::cout << "Solved " << solved << " numbers\n";
272 int sudoku::get_best_guess(int &col, int &row)
275 int min = 0, filled = 0, illegals = 0;
279 * Initialize row and col with illegal values to spot possible
285 for (y = 0; (y < 9) && !illegals; y++)
286 for (x = 0; x < 9; x++) {
287 numbers = get_legal_numbers(x, y);
289 if (numbers == "0") {
294 if (numbers.length() == 0) {
300 min = numbers.length();
306 if ((int)numbers.length() < min) {
307 min = numbers.length();
313 // std::cout << x << "." << y << ": " << " min "
314 // << numbers << col << "." << row << std::endl;
317 if ((!min && !filled) || illegals) {
318 // DPRINT << "Is this sudoku has no solutions?\n";
322 if (!min && (filled == 99)) {
323 DPRINT << "This sudoku is solved\n";
330 sudoku sudoku::solve(int &solvable)
336 // Fill in as much as possible
339 std::cout << std::endl;
342 } while (fill_missing() != 0);
344 ret = get_best_guess(x, y);
346 // Did we solve it yet?
352 std::cout << "This is unsolvable, recursion: "
353 << recursion_depth << std::endl;
360 std::cout << "Solution found , recursion: "
361 << recursion_depth << std::endl;
367 std::cout << "Not solved yet, guessing at depth "
368 << recursion_depth << std::endl;
371 // Try guessim something
372 str = get_legal_numbers(x, y);
373 for (i = 0; i < (int)str.length(); i++) {
375 sudoku guess = *this;
376 guess.set(x, y, str[i]);
379 std::cout << "Guessing number " << str[i] << " to "
380 << x << "." << y << std::endl;
383 guess.recursion_depth = recursion_depth + 1;
386 guess = guess.solve(can_solve);
398 std::vector<sudoku> sudoku::solve_all()
402 std::vector<sudoku> sudokus;
404 // Fill in as much as possible
407 std::cout << std::endl;
410 } while (fill_missing() != 0);
412 ret = get_best_guess(x, y);
414 // Did we solve it yet?
419 std::cout << "This is unsolvable, recursion: "
420 << recursion_depth << std::endl;
426 std::cout << "Solution found , recursion: "
427 << recursion_depth << std::endl;
429 sudokus.push_back(*this);
435 std::cout << "Not solved yet, guessing at depth "
436 << recursion_depth << std::endl;
439 // Try guessim something
440 str = get_legal_numbers(x, y);
441 for (i = 0; i < (int)str.length(); i++) {
442 std::vector<sudoku> results;
444 sudoku guess = *this;
448 std::cout << "Guessing number " << str[i] << " to "
449 << x << "." << y << std::endl;
452 guess.set(x, y, str[i]);
453 guess.recursion_depth = recursion_depth + 1;
456 results = guess.solve_all();
457 guesses += guess.guesses;
460 if (!results.empty()) {
461 /* printf("Got %d solutions, guessed %d: %s\n",
462 (int)results.size(), (int)str.size(),
465 for(j = 0;j < (int)results.size(); j++) {
466 sudokus.push_back(results.at(j));
467 guesses += results.at(j).guesses;
472 std::cout << "Guesses: " << guesses << std::endl;
474 // Return what was solved