# Sudoku problem

• 12-05-2008
Swarvy
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
• 12-05-2008
tabstop
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?
• 12-05-2008
Swarvy
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; }```
• 12-05-2008