Sudoku Brute Forceing
Author
I am trying to solve Sudoku puzzles by means of a brute force method, however I have two big problems.
1) Figuring out the O( ), AKA worst case scenario. I think I figure out how many possible combination of numbers (1-9) can fit in the 9X9 sub square but I need some advice on how to figure out all the possible combinations with all 9 sub squares.Anyone have a clue or hint to hint me in the right directions?
2) I am not sure if my brute force method is correct? If anyone has programmed a Sudoku solver using a brute force method or a similar program using this brute force method, please give me some advice, thanks a bunch!!!
Here is the method I am using to brute force the Sudoku puzzle:
top_left_square = 1;
While(top_left_square <= 9 && !sorted through the other squares as well)
{
/* Sort through every possible combination for all the other squares
besides the given squares */
top_left_square += 1;
if(we solved the puzzle)
{
print the solution;
break;
}
}
so the Sudoku squares would first look like this where the 0 are an instance of an attempted combination of numbers where C are the exceptional unsorted given numbers
10000000
00C0000C
0000C00C
00C0000C
0C00C000
C0000C00
0000000C
00000000
0000000C
when we have sorted through every combination of the C numbers the grid looks like this:
20000000
00C0000C
0000C00C
00C0000C
0C00C000
C0000C00
0000000C
00000000
0000000C
keep sorting and incrementing the top left number till it is at 9 and we sorted all the C numbers ( which then the Sudoku puzzle is invalid) or we solved the puzzle.
This thread sparked my interest because I made a Sudoku solver in C++ that uses a brute-force algorithm (I was super surprised when my little experiment actually worked the first time!! that like...never happens). Take a look:
#include <iostream>#include <sstream>#include <vector>using namespace std;struct digit{ vector <int> can;};struct puzzle{ digit sudoku[9][9];};bool Correct;string Error;bool check(puzzle *p){ if (Correct) { // Make sure there is only one number per box for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (p->sudoku[j].can.size() != 1) return false; } } bool flag[9]; // Check each row for (int i = 0; i < 9; i++) { for (int a = 0; a < 9; a++) flag[a] = false; for (int j = 0; j < 9; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } // Check each column for (int i = 0; i < 9; i++) { for (int a = 0; a < 9; a++) flag[a] = false; for (int j = 0; j < 9; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } // Check each quadrant for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 3; i < 6; i++) { for (int j = 0; j < 3; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 6; i < 9; i++) { for (int j = 0; j < 3; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 0; i < 3; i++) { for (int j = 3; j < 6; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 3; i < 6; i++) { for (int j = 3; j < 6; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 6; i < 9; i++) { for (int j = 3; j < 6; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 0; i < 3; i++) { for (int j = 6; j < 9; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 3; i < 6; i++) { for (int j = 6; j < 9; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } for (int a = 0; a < 9; a++) flag[a] = false; for (int i = 6; i < 9; i++) { for (int j = 6; j < 9; j++) { if (flag[p->sudoku[j].can[0]-1]) return false; flag[p->sudoku[j].can[0]-1] = true; } } } return true;}void autofill(puzzle *p){ if (Correct) { bool Change = true; while (Change) { Change = false; // Autofill the remaining boxes if possible without guessing for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { // If the box is solved, elimitate the possibility in other boxes if (p->sudoku[j].can.size() == 1) { // Determine the quadrant int ioff = 0; int joff = 0; if (i > 2) ioff += 3; if (i > 5) ioff += 3; if (j > 2) joff += 3; if (j > 5) joff += 3; if (!Change) { // Clear the horizontal row for (int y = 0; y < 9; y++) { if (p->sudoku[y].can.size() > 1) { for (int d = 0; d < (int)p->sudoku[y].can.size(); d++) { if (p->sudoku[y].can[d] == p->sudoku[j].can[0]) { if (p->sudoku[y].can.size() > 0) p->sudoku[y].can.erase(p->sudoku[y].can.begin()+d); Change = true; y = 9; break; } } } } } if (!Change) { // Clear the vertical column for (int y = 0; y < 9; y++) { if (p->sudoku[y][j].can.size() > 1) { for (int d = 0; d < (int)p->sudoku[y][j].can.size(); d++) { if (p->sudoku[y][j].can[d] == p->sudoku[j].can[0]) { if (p->sudoku[y].can.size() > 0) p->sudoku[y][j].can.erase(p->sudoku[y][j].can.begin()+d); Change = true; y = 9; break; } } } } } if (!Change) { // Clear the quadrant for (int f = 0; f < 3; f++) { for (int g = 0; g < 3; g++) { if (p->sudoku[ioff+f][joff+g].can.size() > 1) { for (int d = 0; d < (int)p->sudoku[ioff+f][joff+g].can.size(); d++) { if (p->sudoku[ioff+f][joff+g].can[d] == p->sudoku[j].can[0]) { if (p->sudoku[ioff+f][joff+g].can.size() > 0) p->sudoku[ioff+f][joff+g].can.erase(p->sudoku[ioff+f][joff+g].can.begin()+d); Change = true; g = 3; f = 3; break; } } } } } } if (!Change) { // Check if the digit is a number because others in the horizontal row are not for (int b = 0; b < (int)p->sudoku[j].can.size(); b++) { bool Lone = true; for (int y = 0; y < 9; y++) { if (y != j) { for (int d = 0; d < (int)p->sudoku[y].can.size(); d++) { if (p->sudoku[y].can[d] == p->sudoku[j].can) Lone = false; } } } if (Lone) { int x = p->sudoku[j].can; p->sudoku[j].can.clear(); p->sudoku[j].can.push_back(x); break; } } // Check if the digit is a number because others in the vertical column are not for (int b = 0; b < (int)p->sudoku[j].can.size(); b++) { bool Lone = true; for (int y = 0; y < 9; y++) { if (y != j) { for (int d = 0; d < (int)p->sudoku[y][j].can.size(); d++) { if (p->sudoku[y][j].can[d] == p->sudoku[j].can) Lone = false; } } } if (Lone) { int x = p->sudoku[j].can; p->sudoku[j].can.clear(); p->sudoku[j].can.push_back(x); break; } } // Check if the digit is a number because others in the quadrant are not for (int b = 0; b < (int)p->sudoku[j].can.size(); b++) { bool Lone = true; for (int f = 0; f < 3; f++) { for (int g = 0; g < 3; g++) { for (int y = 0; y < 9; y++) { if (y != j) { for (int d = 0; d < (int)p->sudoku[ioff+f][joff+g].can.size(); d++) { if (p->sudoku[ioff+f][joff+g].can[d] == p->sudoku[j].can) Lone = false; } } } if (Lone) { int x = p->sudoku[j].can; p->sudoku[j].can.clear(); p->sudoku[j].can.push_back(x); break; } } } } } } } } if (!Change) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (p->sudoku[j].can.size() > 1) { for (int d = 0; d < (int)p->sudoku[j].can.size(); d++) { // Make a copy of the puzzle so we don't ruin the first one puzzle cpy = (*p); // Assume one of the candidates for a square cpy.sudoku[j].can.clear(); cpy.sudoku[j].can.push_back(p->sudoku[j].can[d]); // Try and solve the new puzzle autofill(&cpy); // Check the result if (check(&cpy)) { (*p) = cpy; return; } } return; } } } } } }}int main(){ cout<< " Sudoku Solver Example:\n" " Version 1.0.1\n" " Stephan Boyer 53xx7xxxx\n" " 6xx195xxx\n" " x98xxxx6x\n" " 8xxx6xxx3\n" " 4xx8x3xx1\n" " 7xxx2xxx6\n" " x6xxxx28x\n" " xxx419xx5\n" " xxxx8xx79\n"; while (true) { Correct = true; // Get the numbers cout<<"\nEnter the numbers like in the example:\n\n"; puzzle in; bool TryAgain = false; for (int i = 0; i < 9; i++) { string line; cin>>line; if (line.size() != 9) { Correct = false; Error = "invalid input ('"+line+"')"; TryAgain = true; break; } for (int j = 0; j < 9; j++) { bool found = false; if (!found) { if (line[j] == 'x') { found = true; for (int c = 0; c < 9; c++) in.sudoku[j].can.push_back(c+1); } } if (!found) { if (line[j] == '1') { found = true; in.sudoku[j].can.push_back(1); } } if (!found) { if (line[j] == '2') { found = true; in.sudoku[j].can.push_back(2); } } if (!found) { if (line[j] == '3') { found = true; in.sudoku[j].can.push_back(3); } } if (!found) { if (line[j] == '4') { found = true; in.sudoku[j].can.push_back(4); } } if (!found) { if (line[j] == '5') { found = true; in.sudoku[j].can.push_back(5); } } if (!found) { if (line[j] == '6') { found = true; in.sudoku[j].can.push_back(6); } } if (!found) { if (line[j] == '7') { found = true; in.sudoku[j].can.push_back(7); } } if (!found) { if (line[j] == '8') { found = true; in.sudoku[j].can.push_back(8); } } if (!found) { if (line[j] == '9') { found = true; in.sudoku[j].can.push_back(9); } } if (!found) { Correct = false; Error = "invalid input ('"+line+"')"; i = 9; j = 9; TryAgain = true; } } } if (TryAgain) { cout<<"\nError: "+Error+"\n"; continue; } // Display a solving message cout<<"\nSolving...\n"; // Solve the puzzle autofill(&in); // Verify the output if (Correct) { if (!check(&in)) { Correct = false; Error = "no solution"; } } // Display the output if (Correct) { cout<<"\nSolution:\n\n"; for (int i = 0; i < 9; i++) { string line; for (int j = 0; j < 9; j++) { ostringstream myStream; myStream<<in.sudoku[j].can[0]<<flush; line += myStream.str().c_str(); if (j == 2 || j == 5) line += " "; if (j < 8) line += " "; } cout<<line<<"\n"; if (i == 2 || i == 5) cout<<"\n"; } } else cout<<"\nError: "+Error+"\n"; } return 0;}
Author
Yes, thank you very much, that gave me some insight.
I still can't find out how to beak down the problem to figure out how many combinations are possible when trying every combination of numbers under the Sudoku rules and then apply that to figure out the number of possibilities with knowledge such as the given numbers and what each squares possible number (candidates)... My idea was to start with a small 1x1 grid with 2 numbers ( which has 2 combinations) and increment the number of rows and columns by one the number of number's accordingly and find a pattern to figure out the formula to find out the number of combinations possible with a 9x9 square with N numbers given and knowing the candidates for each square... This however would take a super long time because before I find a formula, I will have to manually write out the combinations which is impractical for 4x4 squares or greater..
Another solution would figure out how many possibilities there are in each sub square ( quadrant ) and then figure out the number of possibilities with a little bit broken down number squares ( but more of them)...
Any ideas?
I still can't find out how to beak down the problem to figure out how many combinations are possible when trying every combination of numbers under the Sudoku rules and then apply that to figure out the number of possibilities with knowledge such as the given numbers and what each squares possible number (candidates)... My idea was to start with a small 1x1 grid with 2 numbers ( which has 2 combinations) and increment the number of rows and columns by one the number of number's accordingly and find a pattern to figure out the formula to find out the number of combinations possible with a 9x9 square with N numbers given and knowing the candidates for each square... This however would take a super long time because before I find a formula, I will have to manually write out the combinations which is impractical for 4x4 squares or greater..
Another solution would figure out how many possibilities there are in each sub square ( quadrant ) and then figure out the number of possibilities with a little bit broken down number squares ( but more of them)...
Any ideas?
Quote:Original post by ouraqt
This thread sparked my interest because I made a Sudoku solver in C++ that uses a brute-force algorithm (I was super surprised when my little experiment actually worked the first time!! that like...never happens). Take a look:
*** Source Snippet Removed ***
LOL! I know exactly how you feel. I'm just getting to the point where I can write a small program or make a change that works the first time, and it's still a heady feeling!
Actually though, a while ago I came up with a process-of-elimination approach to solving Sudoku puzzles. I attempted to write a program that would do this, but wasn't a good enough programmer and wasn't determined enough. The point is, with a process of elimination type of solution, you don't need to know all the possible combinations of numbers, you just need to follow the logic.
You may need to do a little guessing on sparser puzzles, but not much, especially if you keep it to squares that only have a couple possibilities
First question that comes to mind is, why use brute force? It's fairly easy to use a logical approach to solve sudoku puzzles. I wrote such a solver a couple years ago.
I had a 9x9x9 3D array. The first 2 dimensions were for the grid, and the third dimension was for the possible number for each position in the grid.
Say you have a "1" in a case somewhere in the top row. You can then flag all the "1"'s out of the other sqaures in the top row, and all the "1"'s in that sub square. You repeat that process for all the given numbers a sudoku starts with.
Then you walk the squares and look at the flag numbers left in the third dimension. If there is only a number left, it means it's that numbers place. You can then repeat the process above.
Eventually you may come to a no pass. meaning there are no squares with only one number unflagged. I wrote a recursive function that tries each of the numbers and so on.
Hope it makes sense.
If you are still wondering at the mathematical possibilities of a layout for a grid, they are HUGE! Just for the top row (ignoring the other rows for now) you can have any order of the numbers from 1 to 9. That's 9! (factorial 9) which is 362,880 posibilities, just for the first row. For the second row the possibilities aren't as high cause of the limitations imposed by the first row, but it will still be very high and multiply with the possibilites of 9! of top row. I'm sure if you google it you can find the final possibilites.
From http://www.teachingk-8.com/archives/integrating_math_in_your_classroom/sudoku_by_michael_naylor.html
"There are more than six sextillion (6 followed by 21 zeros) possible 9 x 9 Sudoku answer grids. If you could solve two trillion Sudoku puzzles in a second, you might be able to finish all of the possibilities in 100 years."
I had a 9x9x9 3D array. The first 2 dimensions were for the grid, and the third dimension was for the possible number for each position in the grid.
Say you have a "1" in a case somewhere in the top row. You can then flag all the "1"'s out of the other sqaures in the top row, and all the "1"'s in that sub square. You repeat that process for all the given numbers a sudoku starts with.
Then you walk the squares and look at the flag numbers left in the third dimension. If there is only a number left, it means it's that numbers place. You can then repeat the process above.
Eventually you may come to a no pass. meaning there are no squares with only one number unflagged. I wrote a recursive function that tries each of the numbers and so on.
Hope it makes sense.
If you are still wondering at the mathematical possibilities of a layout for a grid, they are HUGE! Just for the top row (ignoring the other rows for now) you can have any order of the numbers from 1 to 9. That's 9! (factorial 9) which is 362,880 posibilities, just for the first row. For the second row the possibilities aren't as high cause of the limitations imposed by the first row, but it will still be very high and multiply with the possibilites of 9! of top row. I'm sure if you google it you can find the final possibilites.
From http://www.teachingk-8.com/archives/integrating_math_in_your_classroom/sudoku_by_michael_naylor.html
"There are more than six sextillion (6 followed by 21 zeros) possible 9 x 9 Sudoku answer grids. If you could solve two trillion Sudoku puzzles in a second, you might be able to finish all of the possibilities in 100 years."
At first, I was sure there would be an easy way to program a solver for any sudoku. The solver I've programmed really starts with a "logical" solving - it controls rows, columns, squares, etc. After all the possibilities are spent and it is still not solved ... the second section comes up - backtracking :)
the url: http://sudoku.ulesa.cz , it's a Java online web application.
the url: http://sudoku.ulesa.cz , it's a Java online web application.
Here's the source of my logical solver I wrote a while back. Not the prettiest code in the world, but it works. Includes a demo puzzle.
#include "stdafx.h"#include <algorithm>#include <set>#include <vector>#include <cassert>#include <iostream>using std::set;using std::vector;enum BoardResult{ Board_Unsolved, Board_Solved, Board_Bogus};class PositionValue{public: PositionValue() { flags = 1023; // all fields set, i.e. no position known } void ForceValue(int value) { assert(value >= 1 && value <= 9); flags = (1 << value); } // Returns true if the elimination removed a previously possible value bool EliminateValue(int value) { assert(value >= 1 && value <= 9); bool waspossible = ((flags & (1 << value)) != 0); flags &= (~(1 << value)); if(waspossible && ((flags & (1 << value)) == 0)) return true; return false; } set<int> GetPossibleValues() const { set<int> ret; for(int i = 1; i <= 9; ++i) { if(flags & (1 << i)) ret.insert(i); } return ret; } bool IsBogus() const { // If no possible values left, the position is bogus return GetPossibleValues().empty(); }protected: int flags;};typedef vector<PositionValue> PositionList;class Block{public: void Set(int row, int col, int value) { assert(row >= 0 && row <= 2); assert(col >= 0 && col <= 2); values[row][col].ForceValue(value); } PositionList GetRow(int row) const { assert(row >= 0 && row <= 2); PositionList ret; ret.push_back(values[row][0]); ret.push_back(values[row][1]); ret.push_back(values[row][2]); return ret; } PositionList GetCol(int col) const { assert(col >= 0 && col <= 2); PositionList ret; ret.push_back(values[0][col]); ret.push_back(values[1][col]); ret.push_back(values[2][col]); return ret; } PositionValue& GetCell(int row, int col) { assert(row >= 0 && row <= 2); assert(col >= 0 && col <= 2); return values[row][col]; } const PositionValue& GetCell(int row, int col) const { assert(row >= 0 && row <= 2); assert(col >= 0 && col <= 2); return values[row][col]; }protected: PositionValue values[3][3];};class Board{public: void Set(int row, int col, int value) { assert(row >= 0 && row <= 8); assert(col >= 0 && col <= 8); int blockrow = row / 3; int row_withinblock = row % 3; int blockcol = col / 3; int col_withinblock = col % 3; blocks[blockrow][blockcol].Set(row_withinblock, col_withinblock, value); } PositionList GetRow(int row) const { PositionList ret; int blockrow = row / 3; int row_withinblock = row % 3; for(int i = 0; i < 3; ++i) { PositionList t = blocks[blockrow].GetRow(row_withinblock); ret.insert(ret.end(), t.begin(), t.end()); } return ret; } bool Reduce() { bool ret = false; // Eliminate all non-possible value states for(int row = 0; row < 9; ++row) { PositionList rowpositions = GetRow(row); for(int col = 0; col < 9; ++col) { set<int> possibles = GetCell(row, col).GetPossibleValues(); if(possibles.size() == 1) { int value = *possibles.begin(); ret = EliminateRow(row, value, col) || ret; ret = EliminateCol(col, value, row) || ret; ret = EliminateBlock(row / 3, col / 3, value, row % 3, col % 3) || ret; } } } return ret; } bool EliminateRow(int row, int value, int safecolumn) { bool ret = false; for(int i = 0; i < 9; ++i) { if(i == safecolumn) continue; ret = GetCell(row, i).EliminateValue(value) || ret; } return ret; } bool EliminateCol(int col, int value, int saferow) { bool ret = false; for(int i = 0; i < 9; ++i) { if(i == saferow) continue; ret = GetCell(i, col).EliminateValue(value) || ret; } return ret; } bool EliminateBlock(int blockr, int blockc, int value, int safesubr, int safesubc) { bool ret = false; for(int r = 0; r < 3; ++r) { for(int c = 0; c < 3; ++c) { if(r == safesubr && c == safesubc) continue; ret = blocks[blockr][blockc].GetCell(r, c).EliminateValue(value) || ret; } } return ret; } PositionValue& GetCell(int row, int col) { return blocks[row / 3][col / 3].GetCell(row % 3, col % 3); } const PositionValue& GetCell(int row, int col) const { return blocks[row / 3][col / 3].GetCell(row % 3, col % 3); } void Display() const { int fmtrow = 0; std::cout << "BOARD STATE\n"; for(int i = 0; i < 9; ++i) { int fmtcol = 0; PositionList row = GetRow(i); for(PositionList::const_iterator iter = row.begin(); iter != row.end(); ++iter) { const PositionValue& v = *iter; set<int> possibles = v.GetPossibleValues(); if(possibles.empty()) std::cout << "X "; else if(possibles.size() == 1) std::cout << *possibles.begin() << " "; else std::cout << " "; if(++fmtcol == 3) { std::cout << "| "; fmtcol = 0; } } std::cout << "\n\n"; if(++fmtrow == 3) { std::cout << "-----------------------\n\n"; fmtrow = 0; } } std::cout << std::endl; } void DisplayPossibles() const { std::cout << "POSSIBILITIES:\n"; for(int r = 0; r < 9; ++r) { for(int c = 0; c < 9; ++c) { set<int> possibles = GetCell(r, c).GetPossibleValues(); if(possibles.size() > 1) { std::cout << "Row " << r << " col " << c << " - "; for(set<int>::const_iterator iter = possibles.begin(); iter != possibles.end(); ++iter) std::cout << *iter; std::cout << "\n"; } } } std::cout << std::endl; }protected: Block blocks[3][3];};BoardResult GetBoardState(const Board& b){ for(int r = 0; r < 9; ++r) { for(int c = 0; c < 9; ++c) { const PositionValue& v = b.GetCell(r, c); if(v.IsBogus()) return Board_Bogus; size_t numpossible = v.GetPossibleValues().size(); if(numpossible < 1) return Board_Bogus; if(numpossible > 1) return Board_Unsolved; } } return Board_Solved;}void Solve(Board& b){retry: while(b.Reduce()); if(GetBoardState(b) != Board_Solved) { Board b2 = b; // Find a cell with multiple possibilities and speculate on one of them for(int r = 0; r < 9; ++r) { for(int c = 0; c < 9; ++c) { PositionValue& v = b2.GetCell(r, c); set<int> possibles = v.GetPossibleValues(); if(possibles.size() > 1) { int possibleval = *possibles.begin(); v.ForceValue(possibleval); Solve(b2); switch(GetBoardState(b2)) { case Board_Solved: b = b2; return; case Board_Unsolved: return; case Board_Bogus: b.GetCell(r, c).EliminateValue(possibleval); goto retry; default: assert(false); } } } } }}int _tmain(int argc, _TCHAR* argv[]){ Board b; b.Set(0, 4, 9); b.Set(0, 7, 3); b.Set(1, 0, 7); b.Set(1, 2, 2); b.Set(1, 5, 3); b.Set(2, 1, 3); b.Set(2, 4, 4); b.Set(2, 6, 1); b.Set(2, 8, 7); b.Set(3, 3, 1); b.Set(3, 4, 8); b.Set(4, 0, 9); b.Set(4, 1, 8); b.Set(4, 7, 4); b.Set(4, 8, 5); b.Set(5, 4, 2); b.Set(5, 5, 4); b.Set(6, 0, 8); b.Set(6, 2, 5); b.Set(6, 4, 3); b.Set(6, 7, 1); b.Set(7, 3, 6); b.Set(7, 6, 8); b.Set(7, 8, 9); b.Set(8, 1, 6); b.Set(8, 4, 7); b.Display(); int foo; std::cin >> foo; Solve(b); switch(GetBoardState(b)) { case Board_Solved: std::cout << "Board is SOLVED" << std::endl; break; case Board_Unsolved: std::cout << "Board cannot be solved" << std::endl; break; case Board_Bogus: std::cout << "Board is *** BOGUS ***" << std::endl; break; } b.Display(); b.DisplayPossibles(); std::cin >> foo; return 0;}
I got bored and spent about two hours writing this out after thinking out it pretty intently on my way home:
There are several pretty neat things in there if I do say so myself ;)
BTW, ApochPiQ, that's a brutal test case.
#include <cassert>#include <string>#include <iostream>struct invalid_board_state {}; // an exceptionstruct no_solutions {};class Cell { unsigned char lowest_guess; unsigned char guess_flags; // guess_flags is used as a bit field. // Bit 0 is set iff (lowest_guess + 1) is unguessed, bit 1 for // (lowest_guess + 2), etc. This representation makes a lot of operations // easier. public: Cell(): lowest_guess(1), guess_flags(0xff) {} bool known() const { return guess_flags == 0; } int value() const { return known() ? lowest_guess : 0; } // Eliminate a possible option. // Return the known value if it has just become known; 0 otherwise. int reject(int guess) { bool was_known = known(); assert(guess >= 1 && guess <= 9); if (guess < lowest_guess) { return 0; } if (guess > lowest_guess) { guess_flags &= ~(1 << (guess - lowest_guess - 1)); } else { reject_lowest(); } return was_known ? 0 : value(); } void set(int value) { assert(value >= 1 && value <= 9); guess_flags = 0; lowest_guess = value; } void guess_lowest() { guess_flags = 0; } void reject_lowest() { if (known()) { throw invalid_board_state(); } while ((guess_flags & 1) == 0) { guess_flags >>= 1; lowest_guess += 1; } guess_flags >>= 1; lowest_guess += 1; }};std::ostream& operator<<(std::ostream& os, const Cell& c) { return os << c.value();}class Grid { Cell cells[9][9]; int backtracks; void set(int i, int j, int value) { cells[j].set(value); reduce(i, j, value); } void reduce_helper(int x, int y, int value) { int result = cells[x][y].reject(value); if (result != 0) { reduce(x, y, result); } } // Propagate the information that cells in the same row, column and block // are not the given value. Recurse if any new cell values are determined. void reduce(int x, int y, int value) { for (int i = 0; i < 9; ++i) { if (i != x) { reduce_helper(i, y, value); } } for (int j = 0; j < 9; ++j) { if (j != y) { reduce_helper(x, j, value); } } // There are 4 cells in the block which are not in the same row and // column. The following array is used to determine the rows and columns // of those cells: int next[9] = {1, 2, 0, 4, 5, 3, 7, 8, 6}; for (int i = 0; i < 2; ++i) { x = next[x]; for (int j = 0; j < 2; ++j) { y = next[y]; reduce_helper(x, y, value); } } } // Solve the sudoku, given that all cells up until (i, j) are known. void solve(int i, int j) { for (; i < 9; ++i) { for (; j < 9; ++j) { if (!cells[j].known()) { solve_helper(i, j); } } j = 0; } // If we get here, the sudoku is solved. // Otherwise, all possible guesses threw exceptions... } void solve_helper(int i, int j) { Grid backup(*this); try { cells[j].guess_lowest(); reduce(i, j, cells[j].value()); solve(i, j); } catch (invalid_board_state&) { // either bogus reduction, or no solutions with that guess. int b = backtracks; *this = backup; backtracks = b + 1; cells[j].reject_lowest(); if (cells[j].known()) { // If this reduction fails, the parent recursive call made // a bad guess. reduce(i, j, cells[j].value()); } solve(i, j); } } public: // Construct from a string describing each column of each row in turn. // A cell is set to 1 through 9 for characters '1' through '9', and 0 // otherwise. Grid(const std::string& data) : backtracks(0) { if (data.size() != 81) { throw invalid_board_state(); } std::string::const_iterator it = data.begin(); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { int value = *it++ - '0'; if (value >= 1 && value <= 9) { set(i, j, value); } } } try { solve(0, 0); } catch (invalid_board_state&) { throw no_solutions(); } } friend std::ostream& operator<<(std::ostream& os, const Grid& g) { for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { os << g.cells[j]; } os << '\n'; } return os << g.backtracks << " wrong guesses made during solving.\n"; }};int main() { try { std::cout << Grid( "000" "090" "030" "702" "003" "000" "030" "040" "107" "000" "180" "000" "980" "000" "045" "000" "024" "000" "805" "030" "010" "000" "600" "809" "060" "070" "000" ) << std::endl; } catch (no_solutions&) { std::cout << "That sudoku is not solveable" << std::endl; } catch (invalid_board_state&) { std::cout << "Illegal input (or sudoku was found insolvable with only reduction)" << std::endl; }}There are several pretty neat things in there if I do say so myself ;)
BTW, ApochPiQ, that's a brutal test case.
// Spoiler!C:\DOCUME~1\Karl\Desktop>a614798532792513468538246197246185973981367245357924681825439716473651829169872354153 wrong guesses made during solving.// And only two more numbers get filled in by the initial reduction step!// That's only 28 known cells before you have to either guess or use a more// sophisticated reduction method (of which I don't know any).This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
