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; Originally Posted by cyberfish ... determine the square with the fewest possible fillers (and try them first). Ah, that's what ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by cyberfish View Post
    ... determine the square with the fewest possible fillers (and try them first).
    Ah, that's what I was missing. That brings it down to 2.380ms for that hardest board, but I'm doing the timing from within the app itself, so that doesn't include I/O.
    I didn't bother precomputing influences either.
    Last edited by iMalc; 12-06-2008 at 06:55 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    I get 0.003s if I have the whole board filled out in input file... so most of the time is spent in IO. I get the time using the "time" command in my shell (Linux machine).

    But then I used -O3...

    Ah oh well, I don't think it's meaningful comparing times at this magnitude I get significantly different times between different but identical runs, too.

    I think the influences thing, the bitset stuff, and incrementally updating everything are just "linear optimizations" and don't change the complexity.

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Yeah, I'm getting significanty variances between runs also, so there certainly isn't any point comparing speeds, and we're doing much the same thing anyway.
    I'll post mine on my website next time I update it.

    Swarvy: I'm still not sure whether you are trying to solve a sudoku, or generate a new board for a human to solve. Whichever it is, you'll need to show more code.
    I can certainly understand why simply picking random numbers would not be a very good way to solve it, as the chance of the 9 numbers in one 3x3 area having duplicates is very high.
    Last edited by iMalc; 12-06-2008 at 10:32 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195
    I'm trying to make a sudoku generator, its for a game. This is my solution code so far, although it doesn't work how it should.

    Code:
    /* solution.cpp */
    
    #include "solution.h"
    
    void GAME_SOLUTION::GenerateSolution()
    {
         /* This method generates a solution which the user must then try and get.
            The way this method will work, is by going through the grid, 1 square at
            a time, and randomly selecting a number. It will then check in turn if
            there is another number either in the smaller 3x3 grid, the same row or
            the same column, if there is, then another number is selected until 1
            fits.
         */
         
         int idx1,idx2,ret=0;
         int num1;
         
         for(idx1=0; idx1<BUTTON_NUM; idx1++)
         {
                     for(idx2=0; idx2<BUTTON_NUM; idx2++)
                     {
                                 do
                                 {
                                                    ret = 0;
                                                    num1 = (rand()%BUTTON_NUM) + 1;
                                                    
                                                    /* Do the tests */
                                                    ret += this->TestRow(num1, idx1);
                                                    ret += this->TestColumn(num1, idx2);
                                                    ret += this->TestSmallGrid(num1, (int)(idx1/3), (int)(idx2/3));
                                                    
                                                    /* Correct any potential errors */
                                                    ret = this->CorrectError(num1, idx2, idx1, ret);
                                 } while(ret != 0);
                                 
                                 this->SetSolution(num1, idx2, idx1);
                     }
         }
         
         return;
    }
    
    bool GAME_SOLUTION::CorrectError(int num, int idx_x, int idx_y, int ret)
    {
         /* This tests to see if another number which has already been placed can be
            replaced by the one listed to be put down.
         */
         int idx0,idx1;
         int ret2=0,val=0;
         
         if(ret != 0)
         {
                for(idx0=0; idx0<=idx_y; idx0++)
                {
                            if(idx0 == idx_y)
                            {
                                    for(idx1=0; idx1<idx_x; idx1++)
                                    {
                                                /* Check if the number fits */
                                                ret2 = 0;
                                                
                                                val = this->GetSolution(idx1, idx0);
                                                
                                                ret2 += this->TestRow(val, idx_y);
                                                ret2 += this->TestColumn(val, idx_x);
                                                ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3));
                                                
                                                ret2 += this->TestRow(num, idx0);
                                                ret2 += this->TestColumn(num, idx1);
                                                ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3));
                                                
                                                if(ret2 == 0)
                                                {
                                                       this->SetSolution(num, idx1, idx0);
                                                       this->SetSolution(val, idx_x, idx_y);
                                                       return false;
                                                }
                                    }
                            }
                            else
                            {
                                for(idx1=0; idx1<BUTTON_NUM; idx1++)
                                {
                                            /* Check if the number fits */
                                                ret2 = 0;
                                                
                                                val = this->GetSolution(idx1, idx0);
                                                
                                                ret2 += this->TestRow(val, idx_y);
                                                ret2 += this->TestColumn(val, idx_x);
                                                ret2 += this->TestSmallGrid(val, (int)(idx_x/3), (int)(idx_y/3));
                                                
                                                ret2 += this->TestRow(num, idx0);
                                                ret2 += this->TestColumn(num, idx1);
                                                ret2 += this->TestSmallGrid(num, (int)(idx1/3), (int)(idx0/3));
                                                
                                                if(ret2 == 0)
                                                {
                                                       this->SetSolution(num, idx1, idx0);
                                                       this->SetSolution(val, idx_x, idx_y);
                                                       return false;
                                                }
                                }
                            }
                }
         }
                    
         return false;
    }
    
    bool GAME_SOLUTION::TestRow(int num, int idx_y)
    {
         /* This method tests if there are two identical values in the same row */
         int idx=0;
         
         for(idx=0; idx<BUTTON_NUM; idx++)
         {
                    if(num == this->solution[idx][idx_y])
                    {
                                                  return true;
                    }
         }
         
         return false;
    }
    
    bool GAME_SOLUTION::TestColumn(int num, int idx_x)
    {
         /* This method tests if there are two identical values in the same column */
         int idx=0;
         
         for(idx=0; idx<BUTTON_NUM; idx++)
         {
                    if(this->solution[idx_x][idx] == num)
                    {
                                                  return true;
                    }
         }
         
         return false;
    }
    
    bool GAME_SOLUTION::TestSmallGrid(int num, int idx1, int idx2)
    {
         int idx,idx0;
         
         for(idx=0; idx<(BUTTON_NUM/3); idx++)
         {
                    for(idx0=0; idx0<(BUTTON_NUM/3); idx0++)
                    {
                                if(this->solution[(3*idx1) + idx0][(3*idx2) + idx] == num)
                                {
                                                           return true;
                                }
                    }
         }
         
         return false;
    }
    
    void GAME_SOLUTION::ClearSolution()
    {
         /* This clears a solution ready for the next game */
         int idx1, idx2;
         
         for(idx1=0; idx1<BUTTON_NUM; idx1++)
         {
                     for(idx2=0; idx2<BUTTON_NUM; idx2++)
                     {
                                 this->solution[idx2][idx1] = 0;
                     }
         }
         
         /* This seeds the RNG */
         time(&(this->rand_num1));
         srand((unsigned int)(this->rand_num1));
         
         return;
    }
    
    void GAME_SOLUTION::SetSolution(int num, int idx_x, int idx_y)
    {
         /* This method just sets a solution value */
         this->solution[idx_x][idx_y] = num;
         
         return;
    }
    
    unsigned int GAME_SOLUTION::GetSolution(int idx_x, int idx_y)
    {
             /* This returns the solution value for a given position */
             /* The check for the win will be made in main.cpp, in the form of a function call
                to here inside a loop, checking if game_board gives the same result
             */
             
             unsigned int num;
             
             num = this->solution[idx_x][idx_y];
             
             return num;
    }

  5. #20
    The larch
    Join Date
    May 2006
    Posts
    3,573
    So, does it work?

    I think I got somewhat the idea, but suppose in the first line you have

    Code:
    2 7 8 9 3 1 5 _
    and now you get a random number and if it conflicts somewhere you see if you can swap it with something in the same line? As long as the random number is not 4 or 6 this will be a wasted effort.

    I guess also that it might still create a situation where no matter what number you pick, it conflicts and cannot be swapped either to remove the conflict and the program goes into an infinite loop.

    However, I notice that CorrectError always returns false?!
    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).

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Okay. You should know that generating a useful board is usually harder than solving one. Published ones are specifically generated in such a way as to make them solveable by a (more-or-less average) human. Generating boards randomly will usually give you something that is pretty expert level.

    I'm still thinking of starting out into writing as board generator and my current idea involves evaluating how many levels of recursion a solver would have to go into to discover that a guess was incorrect, for each human solver's move.
    Still, that only helps gauge the difficulty of a board, not to actually make it easy to begin with, so it would have to repeatedly generate boards until it found an easy one.
    Another way might be to simply count the number of steps my solver takes in solving it.

    Just be aware that what you're trying to do might be out of your league, and if the above ideas don't pan out, then perhaps mine as well at this stage.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #22
    The larch
    Join Date
    May 2006
    Posts
    3,573
    My puzzle generator works as follows:
    1) create a random solution (code posted above)
    2) pick a number of clues from the solution as opened
    3) try to solve the resulting puzzle using a variety of logical methods (single candidate in a cell, single occurrence of a candidate in a group, pairs, triples etc)
    4) if not successful pick a symmetric pair of additional clues - I think my criteria is a pair of cells that together have the greatest number of candidates - and repeat 3)
    5) to minimize number of clues randomize the order in which clues where opened and try to solve the puzzle with logical methods removing each pair of clues in turn, if puzzle is solvable remove this clue-pair else put it back and try next (since initially about half the grid is given, most of the work is done in this step)
    6) finally solve the puzzle one more time to assess difficulty (could be also done during all previous steps): note each solving technique required as well as a weighted sum of steps - for simple techniques like finding a "naked pair" add less than for a more advanced technique such as a "hidden triple". (The resulting assessment is not entirely satisfactory, though.)

    Also, I discard puzzles that have more than 30 clues (unless in an ultra-beginner mode where you select the number of clues between 30 and 60 and where clues are just added as needed).

    This is a bit slow, though, producing 1000 puzzles in 5 seconds (one a relatively fast computer) which is a problem because stumbling upon a sudoku that would be rated as "evil" might take generating about 30 - 100 (in worst cases about 200) puzzles - most of which are "easy" and "normal". But this is solved by having a background thread occasionally wake up, check if there are enough puzzles of each difficulty in store and make more as needed. So it may not be suitable if your aim is just to produce masses of puzzles as quickly as possible.
    Last edited by anon; 12-08-2008 at 04:41 AM.
    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 2 of 2 FirstFirst 12
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, 08:30 PM
  2. 25x25 sudoku
    By cyberfish in forum C++ Programming
    Replies: 27
    Last Post: 06-23-2009, 02:20 AM
  3. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  4. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM
  5. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 07:46 AM

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