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

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?

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;
}

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.

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.