Thread: Sudoku problem

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

    Sudoku problem

    I'm having a real problem coming up with an algorithm which generates a sudoku problem. all the methods basically come down to selecting a random value for a given space, and providing there isnt the same value in the same column, row or small grid, then it places it there, if not it picks another random value, and repeats till it finds 1 which fits. But I still don't understand what that method doesn't work. It makes sense in my head. But I was wondering if someone could help me out, cos I'm having trouble. I've changed my code a bit, since my last post about this in the C++ board. But here is the updated stuff:

    Code:
    int idx1=0,idx2=0,ret=0;
         int num1;
         
         for(idx1=0; idx1<BUTTON_NUM_Y; idx1++)
         {
                     for(idx2=0; idx2<BUTTON_NUM_X; idx2++)
                     {
                                 do
                                 {
                                                    ret = 0;
                                                    num1 = (rand()&#37;(NUM_BUTTONS-1)) + 1;
                                                    
                                                    /* Do the tests */
                                                    ret += this->TestRow(num1, idx1);
                                                    ret += this->TestColumn(num1, idx2);
                                                    ret += this->TestSmallGrid(num1, (int)(idx1/3), (int)(idx2/3));
                                 } while(ret != 0);
    
                                 // Save the number here
                                 this->SetSolution(num1, idx2, idx1);
    
                     }
         }
    edit: All the check methods return bool. Returns 0 for ok, and 1 is there is a clash
    Last edited by Swarvy; 12-05-2008 at 07:27 PM. Reason: Add more detail to the post

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So suppose you pick some numbers, and you get to here:
    Code:
    146358279
    83517246.
    .
    .
    .
    .
    .
    .
    What number are you going to use to fill the second row? And now, how are you going to fix this?

  3. #3
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195
    That is a good point. I didn't think of that case. I would say that the obvious solution would be to look back through the row, for numbers which would be eligible to swap. and just to make it easy, lets say that it just swaps with the first 1 it comes across which it is allowed to swap with. I've rewritten my code. This is what it looks like atm, with the new method, but its not quite going as planned.

    Code:
    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_Y; idx1++)
         {
                     for(idx2=0; idx2<BUTTON_NUM_X; idx2++)
                     {
                                 do
                                 {
                                                    ret = 0;
                                                    num1 = (rand()%(NUM_BUTTONS-1)) + 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)
    {
         if(ret != 0)
         {
                int idx=0;
                int val=0;
                
                for(idx=0; idx<(idx_x-1); idx++)
                {
                           if(!(this->TestSmallGrid(num, (int)(idx/3), (int)(idx_y/3))))
                           {
                                                         val = this->solution[idx][idx_y];
                                                         this->solution[idx][idx_y] = num;
                                                         this->solution[idx_x][idx_y] = val;
                                                         return false;
                           }
                }
         }
                    
         return true;
    }
    
    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_X; 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_Y; 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_Y/3); idx++)
         {
                    for(idx0=0; idx0<(BUTTON_NUM_X/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_Y; idx1++)
         {
                     for(idx2=0; idx2<BUTTON_NUM_X; 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;
    }

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I still don't see where the checker backs up to a previous square and tries other values there, when the square being checked has no possible legit values.

    Also, remember that some puzzle grids will have many solutions if they are not proven to have just one solution, you can't take that for granted.

    May I suggest a visit to the Sudoku Programmers Forum? Several authors have described their puzzle-making program's algorithm. http://www.setbb.com/sudoku/

    and can speak authoritatively, on this subject.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Basically you just can't create a sudoku (in meaningful time) by just throwing random values into the cells (although my first approach was pretty much random too - and if it failed a certain number of times it would go back a bunch of lines and start over). You need a more systematic approach that wouldn't try the same non-working values over and over and would do something intelligent when it discovers that it has cornered itself.
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM