The algorithm includes sudoku solver, sudoku generator and difficulty analysis. I searched online but still couldn't figure out how. Please help me by explaining the algorithm step by step. Thanks for your inputs.
Printable View
The algorithm includes sudoku solver, sudoku generator and difficulty analysis. I searched online but still couldn't figure out how. Please help me by explaining the algorithm step by step. Thanks for your inputs.
Dear dullboy,
What do you expect here?
I wrote a sudoku game by my own. It was fun programming it.
Do you really want me to post the code? This won't be fun for you...
I recommend you to do it by your own. If you encounter specific questions feel free to ask the experts here. But neither expect someone to post a full algorithm nor someone to post a full source code.
Some hints for a start:
First I implemented the UI ("game engine"): displaying the field, handling mouse clicks (and keyboard events).
The "solver" algo can be the easiest part: Since the program knows all the "hidden" numbers and can simply show them ;)
But: While implementing the "generator" you probably will encounter difficulties.
I did the dirt-and-easy way: I implemented a solver by simply implementing all the solving rules I know (and some I found by the help of Mrs. Google).
Now my generator does the following: It generates a random game, which follows the rules of sudoku (each row, each caret and each column can contain every number only once). The algo is not too hard to implement...
Then I hide all the fields and re-open some of them.
Then - using my solver algo I try to solve the sudoku: If the program finds a solution the generator has finished, if not I open the next field (by random) and try again.
The sudokus generated by my program are difficult enough to be played (at least by myself).
The more rules you implement the more difficult the sudokus will be.
Enjoy programming!
With regards
Programartist
Thanks for your great response. I have several questions regarding your generator. When you have a fully filled sudoku, you hide all the fields and then re-open some of them. How many fields are you going to open and how do you pick the numbers and their position? Also when you use your solver to solve the sudoku, if the program finds a solution, how do you know if the solution is unique? Thanks for your inputs.Quote:
Originally Posted by ProgramArtist
Hi dullboy,
I've been on holiday that's why my answer took some time...
Actually you can try to find out the best count.Quote:
Originally Posted by dullboy
If you have a complete "closed" sudoku (all fields are empty) then you know for sure that is impossible to solve it (by given rules). According to the wikipedia the "the lowest number yet found for the standard variation without a symmetry constraint is 17". That's why you can "open" at least 17 to get good results in an acceptable time.
I pick them randomly. Maybe there are better ways to find "easy"/"medium" and "hard" sudokus but I've never tried it.
My algo stops exactly when the rules can be used to solve the sudoku. Every rule is a "unique" rule: A rule is actually to say: "I can open this field (write a certain "unique" number on it)". While using only unique rules this solution must be unique.Quote:
Originally Posted by dullboy
With regards
Programartist
Thanks for your response. Actually I almost finished the program. I have a question here. Suppose I try to fill in a completely empty board. First of all, I pick up 9 numbers randomly for the first row, say for example, 2, 6, 3, 1, 9, 7, 5,8, 4. I wonder if there is ALWAYS at lease one solution to fill in the whole board successfully based on the first row? Thanks for your inputs.Quote:
Originally Posted by ProgramArtist
I didn't get the point of your response.Quote:
Originally Posted by dullboy
On the one side you're saying that you "almost finished the program". On the other side (If I understand you right) it seems that you're implementing the first task (filling the sudoku array field with random counts following the sudoku rules).
To fill the fields initially:
Pseudo-Code:
With friendly regardsCode:// CX is the size of the field (usually 9)
// IsFieldPossible(x,line,number) must be implemented so that it returns TRUE if it is still possible
// to set number at (x,line) , otherwise it must return FALSE
// The implementation is not shown here.
// this code is MFC (using CList template) but can be easy ported to c++ (using std::vector)
// RND(min,max) should be a macro to get a random integer between (incl) min and max
// #define RND(min,max) ((rand()*(((max)+1)-(min)))/RAND_MAX + (min))
// Set(x,line,number) should be implemented as a function that sets the internal value
for (int number=1; number<CX+1; number++)
{
for (int line=0;line<CY;line++)
{
CList<CPoint,CPoint> possibilities;
while (possibilities.GetCount()) possibilities.RemoveHead();
for (int x=0;x<CX;x++)
{
if (IsFieldPossible(x,line,number))
{
possibilities.AddTail(CPoint(x,line));
}
}
POSITION pos = possibilities.FindIndex(RND(0,possibilities.GetCount()-1));
if (pos)
{
CPoint pt = possibilities.GetAt(pos);
Set(pt.x,pt.y,number);
}
else
{
//TRACE("No place for this number! (should not occur!) (%d) (%d)\n", number, line);
// if you reach this line: Try again to fill in the fields ...
}
}
}
Programartist
The Sodoku game isn't more complex than it's possible to find all solutions.Quote:
Originally Posted by dullboy
You simply make an exhaustive combinatorial search using recursion. You place numbers systematically one by one until you cannot place anymore numbers. If the square is full you've found a solution. But regardless of that the algorithm backtracks recursively and tries other numbers until all possible number combinations have been checked. In principle the algoritm generates all possible ways numbers can be placed on the square. When this process is finished you've found all solutions there are (if any).
An explanation of a few different algorithms (including brute force): "Algorithmics of sudoku" at http://en.wikipedia.org/wiki/Algorithmics_of_sudoku