Sudoku solution generator algorithm

This is a discussion on Sudoku solution generator algorithm within the C++ Programming forums, part of the General Programming Boards category; I'm making a sudoku game using the win32 api atm, but for some reason, I can't seem to get my ...

  1. #1
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195

    Sudoku solution generator algorithm

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  3. #3
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195
    Quote Originally Posted by tabstop View Post
    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.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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....
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    My program find out that there is no solution in 0.005s wall time (including reading in the file).

  11. #11
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    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:
    859612437
    723854169
    164379528
    986147352
    375268914
    241593786
    432981675
    617425893
    598736241

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    Quote Originally Posted by cyberfish View Post
    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.
    Last edited by iMalc; 12-06-2008 at 05:15 PM.

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    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]
    Attached Files Attached Files
    Last edited by cyberfish; 12-06-2008 at 05:14 PM.

  15. #15
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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...
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku solver...
    By matsp in forum C++ Programming
    Replies: 24
    Last Post: 02-14-2011, 07:30 PM
  2. 25x25 sudoku
    By cyberfish in forum C++ Programming
    Replies: 27
    Last Post: 06-23-2009, 01:20 AM
  3. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 03:28 PM
  4. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 10:39 PM
  5. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 06:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21