Sudoku solution generator algorithm

**Swarvy** · 12-04-2008

I'm making a sudoku game using the win32 api atm, but for some reason, I can't seem to get my solution generator method to work as it should.

The way that I'm doing it, is like this (it's not the most efficient way of doing it, but atm, thats not my main concern):
It cycles through the smaller 3x3 grids one by one, randomly selecting an x and y coordinate, and provided that neither the column or the row it selects already has that number, and the square is empty, it places the number there. It first cycles through and places all the 1s, then all the 2s etc. The problem is, I'm still ending up with problems. This is my source code so far (all variables init to zero)...

Code:

for(idx0=1; idx0<NUM_BUTTONS; idx0++)
     {
                 for(idx1=0; idx1<(BUTTON_NUM_Y/3); idx1++)
                 {
                             for(idx2=0; idx2<(BUTTON_NUM_X/3); idx2++)
                             {
                                         /* Generate x and y values, making sure not to have two in the same row or column */
                                         
                                         do
                                         {
                                                     num1 = rand()%3 + (3*idx2);
                                                     num2 = rand()%3 + (3*idx1);
                                                     
                                         } while( (this->solution[num1][num2] != 0)&&((temp_x[num1] == 1)||(temp_y[num2] == 1)) );
                                         
                                         /* Change the index for future numbers */
                                         temp_x[num1] = 1;
                                         temp_y[num2] = 1;
                                         
                                         /* If it gets this far, it's a good value, so record it */
                                         this->solution[num1][num2] = idx0;
                             }
                 }
                 
                 /* Reset the temporary array */
                 for(idx3=0; idx3<(NUM_BUTTONS - 1); idx3++)
                 {
                             temp_x[idx3] = 0;
                             temp_y[idx3] = 0;
                 }
     }

The temp_x and temp_y variables are used to keep track which columns and rows there are already values in. They are reset once the next number to place on the board is selected. I end up with some strange program output from this. although I can't find the bug anywhere.

**tabstop** · 12-04-2008

I would say that your do-while loop needs || where it has && (your program will cheerfully overwrite a previously-filled square, if the temp_x/temp_y check fails).

**Swarvy** · 12-04-2008

Originally Posted by tabstop

I would say that your do-while loop needs || where it has && (your program will cheerfully overwrite a previously-filled square, if the temp_x/temp_y check fails).

I thought that, but when I try that, it just forms an infinite loop, and doesn't knock out any numbers at all, I'm not entirely sure why, cos when I try and follow the logic through in my head, it seems to work, but as that person from Little Britain says - "Computer says no", lol.

**tabstop** · 12-04-2008

Wait -- you weren't expecting an infinite loop? Why not? If you don't luck into building something solvable (or if you're trying to solve a given puzzle, if you don't luck into placing every single number correctly), then all you're going to do is go around and around trying to place a 1 where it can't go.

**matsp** · 12-05-2008

To solve something like this using brute force, you will need to have some way of undoing your so far solution when you end up in a "dead-end" - just like solving by hand, if you got something wrong in one place, you can't solve it, and you'll have to back up all the numbers you've done since you got something wrong (I usually just give up at that point, but I'm not a computer). I did solution that uses recursion to solve the problem. A Sudoku that is REALLY HARD takes about 3 seconds on my quite old PC [that's not a challenge - I'm convinced that if I spent some more time on the project, I'd get it to about half that].

--
Mats

**anon** · 12-05-2008

Not an expert, but I have generated full boards by using a backtracking algorithm (try to solve each cell in order by trying numbers in order in them), and letting it solve an empty grid by randomizing the order numbers will be tried for each cell.

A Sudoku that is REALLY HARD takes about 3 seconds on my quite old PC [that's not a challenge - I'm convinced that if I spent some more time on the project, I'd get it to about half that].

I think for brute-force algorithms there are no significant differences in difficulty (although it might help if you could, for example, eliminate a lot of single-candidate cells), but how long would something like this take?

Code:

.........
.........
.........
.........
........1
........2
........3
........4
56789....

**matsp** · 12-05-2008

As I haven't got my code here at work, I don't know how long that would take - if I get time to do it at the weekend (unlikely) I will report back - Since there are likely many different solutions to such a sparsely filled board, I guess it will actually be better.

By the way, my solution uses a sequential approach rather than random number, based on "what numbers are possible in this position". I'm not trying to fill a board to make a "new game" - that is a goal in the future, but right now it's not yet there.

--
Mats

**anon** · 12-05-2008

As I haven't got my code here at work, I don't know how long that would take - if I get time to do it at the weekend (unlikely) I will report back - Since there are likely many different solutions to such a sparsely filled board, I guess it will actually be better.

There are actually no solutions - what goes into the bottom-right corner (but how long would it take to find out?)

In my program that would take forever (since it would need to backtrack the whole solution and try every possible combination before giving up). Therefore it first sees if there are cells with no candidates (and another condition in which puzzles are unsolvable - I think groups that don't contain all numbers among candidates|given cells) and exits immediately.

**matsp** · 12-05-2008

Originally Posted by anon

There are actually no solutions - what goes into the bottom-right corner (but how long would it take to find out?)

In my program that would take forever (since it would need to backtrack the whole solution and try every possible combination before giving up). Therefore it first sees if there are cells with no candidates (and another condition in which puzzles are unsolvable - I think groups that don't contain all numbers among candidates|given cells) and exits immediately.

I don't know if my code figures out that it's unsolvable - it's a good point. Again, given time, I will test it and fix as appropriate. But I don't get much time for hobby projects.

--
Mats

**cyberfish** · 12-05-2008

My program find out that there is no solution in 0.005s wall time (including reading in the file).

**cyberfish** · 12-05-2008

Solves this puzzle -
http://www.usatoday.com/news/offbeat...6-sudoku_x.htm
(Google for "hardest sudoku puzzle"

)

in 0.004s including IO. (0.005s was on a network drive)

Code:

85...24..
72......9
..4......
...1.7..2
3.5...9..
.4.......
....8..7.
.17......
....36.4.

Code:

**anon** · 12-06-2008

That's an interesting claim because the puzzle seemed quite straightforward to solve. Unfortunately my program does not have the option to display the difficulty rating of a given puzzle but it doesn't seem to require any techniques that would make it go beyond Medium on my system (assessing difficulty is another big question in generating sudokus, though).

**iMalc** · 12-06-2008

Originally Posted by cyberfish

Solves this puzzle -
http://www.usatoday.com/news/offbeat...6-sudoku_x.htm
(Google for "hardest sudoku puzzle"

)

in 0.004s including IO. (0.005s was on a network drive)

That's very impressive!

Mine reports taking 52.506ms on the one you posted, and discovers the one anon posted is unsolveable in 0.003ms. Easy ones seem to take around 0.569ms.
I haven't done anything towards guaging the level of difficulty for a human solver, nor do I make any attempt to verify that the provided board does not have multiple solutions.
So, what's your secret in solving that hard one really fast?

anon: Although the one cyberfish posted is unbelieveably hard for human solvers, ALL sudoku's are easy for a reasonable backtracking computer program solver to solve.

Swarvy: Sorry I haven't written a Sudoku board generator, if that's what you are trying to do.

**cyberfish** · 12-06-2008

I wrote it a few months back for practice (and I have only been programming for a year or so...) so the code is quite unreadable. I can't seem to figure out exactly how it works from a glance

.

I think the key is to do a lot of precomputation. Things like whether a square belongs in a "group", and an array (I think I used a bitset) of squares "influenced" by setting a square (only they need to be checked when a new square is filled in). The board is also incrementally updated, containing a 2D boolean array of possible "fillers" for squares (1D array of bitsets in my case, since it allows fast checking of board legality. If a square has no possible fillers, that is, the bitset == 0, the board is illegal).

Bitsets help because they allow fast checking for 0, and also extracting the most significant or least significant bits set to 1 (bit scan forward or bit scan reverse, can even be precomputed, avoiding lots of loops). Also, popcounting (can again be precomputed) can be used to quickly determine the square with the fewest possible fillers (and try them first).

The code is attached if anyone is interested.

[edit]
oh and I think I used
__builtin_popcount()
and
__builtin_ctz()

so it will probably only work with gcc/icc.
[/edit]

**anon** · 12-06-2008

Well, I have used the following code to generate a random solution. It is entirely "invented here" without much knowledge in the theory of sudoku programming and may not be too good at all.

This too uses bit-fiddling (for the purposes of the rest of the generator) and even the output is in binary, hence the log calculation to convert the output into human readable format

I guess lines like

Code:

int b = r - r &#37; 3 + c / 3;

show that some things could have been precomputed.

Code:

#include <iostream>
#include <algorithm>
#include <ctime>
#include <cmath>

bool solve_recursive(unsigned full[9][9], int r, int c,
    unsigned candidates[9][9][9], unsigned row[9], unsigned col[9], unsigned box[9])
{
    ++c;
    if (c == 9) {
        ++r;
        c = 0;
        if (r == 9)
            return true;
    }

    if (full[r][c])
        return solve_recursive(full, r, c, candidates, row, col, box);

    int b = r - r % 3 + c / 3;

    unsigned free = 511 ^ (row[r] | col[c] | box[b]);
    if (!free) return false;
    for (int i = 0; i < 9; ++i) {
        if (candidates[r][c][i] & free) {
            row[r] |= candidates[r][c][i];
            col[c] |= candidates[r][c][i];
            box[b] |= candidates[r][c][i];
            full[r][c] = candidates[r][c][i];
            if (solve_recursive(full, r, c, candidates, row, col, box))
                return true;
            row[r] ^= candidates[r][c][i];
            col[c] ^= candidates[r][c][i];
            box[b] ^= candidates[r][c][i];
            full[r][c] = 0;
        }
    }
    return false;
}

bool generate_random_solution(unsigned full[9][9])
{
    unsigned candidates[9][9][9];
    unsigned row[9] = {0}, col[9] = {0}, box[9] = {0};

    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            for (int i = 0; i < 9; ++i) {
                candidates[r][c][i] = 1 << i;
            }

            std::random_shuffle(candidates[r][c], candidates[r][c]+9);
            full[r][c] = 0;
        }
    }

    return solve_recursive(full, -1, 8, candidates, row, col, box);
}


int main()
{
    srand(time(0));
    unsigned puzzle[9][9];
    generate_random_solution(puzzle);

    for (int i = 0; i != 9; ++i) {
        for (int j = 0; j != 9; ++j) {
            std::cout << log2(puzzle[i][j])  + 1 << ' ';
        }
        std::cout << '\n';
    }
}

anon: Although the one cyberfish posted is unbelieveably hard for human solvers

It didn't seem to be hard at all - and that's without guessing as sudoku should be solved...

Thread: Sudoku solution generator algorithm

Thread Tools

Search Thread

Display

Sudoku solution generator algorithm

Similar Threads

Sudoku solver...

25x25 sudoku

Help for a sudoku Solver

Sudoku - the new addiction

anyone know the solution?