Any guru here can explain algorithm for Sudoku?

[dullboy]

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.

[ProgramArtist]

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

[dullboy]

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.

[ProgramArtist]

Hi dullboy,

I've been on holiday that's why my answer took some time...

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?

Actually you can try to find out the best count.
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.

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.

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.

With regards
Programartist

[dullboy]

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

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.

[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.

I didn't get the point of your response.

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:

    // 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 ...
            }
        }
    }

With friendly regards
Programartist

[nuzzle]

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.

The Sodoku game isn't more complex than it's possible to find all solutions.

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).

[MikeAThon]

An explanation of a few different algorithms (including brute force): "Algorithmics of sudoku" at http://en.wikipedia.org/wiki/Algorithmics_of_sudoku