Sign in to follow this  
Mad_Coder

Sudoku Brute Forceing

Recommended Posts

Mad_Coder    100
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.

Share this post


Link to post
Share on other sites
ouraqt    236
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[i][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[i][j].can[0]-1])
return false;
flag[p->sudoku[i][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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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][i].can[0]-1])
return false;
flag[p->sudoku[j][i].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[i][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[i][y].can.size() > 1)
{
for (int d = 0; d < (int)p->sudoku[i][y].can.size(); d++)
{
if (p->sudoku[i][y].can[d] == p->sudoku[i][j].can[0])
{
if (p->sudoku[i][y].can.size() > 0)
p->sudoku[i][y].can.erase(p->sudoku[i][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[i][j].can[0])
{
if (p->sudoku[i][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[i][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[i][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[i][y].can.size(); d++)
{
if (p->sudoku[i][y].can[d] == p->sudoku[i][j].can[b])
Lone = false;
}
}
}
if (Lone)
{
int x = p->sudoku[i][j].can[b];
p->sudoku[i][j].can.clear();
p->sudoku[i][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[i][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[i][j].can[b])
Lone = false;
}
}
}
if (Lone)
{
int x = p->sudoku[i][j].can[b];
p->sudoku[i][j].can.clear();
p->sudoku[i][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[i][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[i][j].can[b])
Lone = false;
}
}
}
if (Lone)
{
int x = p->sudoku[i][j].can[b];
p->sudoku[i][j].can.clear();
p->sudoku[i][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[i][j].can.size() > 1)
{
for (int d = 0; d < (int)p->sudoku[i][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[i][j].can.clear();
cpy.sudoku[i][j].can.push_back(p->sudoku[i][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[i][j].can.push_back(c+1);
}
}
if (!found)
{
if (line[j] == '1')
{
found = true;
in.sudoku[i][j].can.push_back(1);
}
}
if (!found)
{
if (line[j] == '2')
{
found = true;
in.sudoku[i][j].can.push_back(2);
}
}
if (!found)
{
if (line[j] == '3')
{
found = true;
in.sudoku[i][j].can.push_back(3);
}
}
if (!found)
{
if (line[j] == '4')
{
found = true;
in.sudoku[i][j].can.push_back(4);
}
}
if (!found)
{
if (line[j] == '5')
{
found = true;
in.sudoku[i][j].can.push_back(5);
}
}
if (!found)
{
if (line[j] == '6')
{
found = true;
in.sudoku[i][j].can.push_back(6);
}
}
if (!found)
{
if (line[j] == '7')
{
found = true;
in.sudoku[i][j].can.push_back(7);
}
}
if (!found)
{
if (line[j] == '8')
{
found = true;
in.sudoku[i][j].can.push_back(8);
}
}
if (!found)
{
if (line[j] == '9')
{
found = true;
in.sudoku[i][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[i][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;
}


Share this post


Link to post
Share on other sites
Mad_Coder    100
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?

Share this post


Link to post
Share on other sites
theOcelot    498
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

Share this post


Link to post
Share on other sites
Hexmind    871
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."

Share this post


Link to post
Share on other sites
brundibar    122
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.

Share this post


Link to post
Share on other sites
ApochPiQ    23064
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][i].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;
}

Share this post


Link to post
Share on other sites
Zahlman    1682
I got bored and spent about two hours writing this out after thinking out it pretty intently on my way home:


#include <cassert>
#include <string>
#include <iostream>

struct invalid_board_state {}; // an exception
struct 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[i][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[i][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[i][j].guess_lowest();
reduce(i, j, cells[i][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[i][j].reject_lowest();
if (cells[i][j].known()) {
// If this reduction fails, the parent recursive call made
// a bad guess.
reduce(i, j, cells[i][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[i][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>a
614798532
792513468
538246197
246185973
981367245
357924681
825439716
473651829
169872354
153 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).




Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this