Member Avatar for alexanderlegend

Hello everyone!
I have been working on a sudoku generator. My main aim is to create a completed 9x9 grid that follows the rules of sudoku. The grid should display unique numbers every time it is run i.e the numbers have to be randomised.

My logic in tackling the problem is as follows:

1.Create a 9x9 array and fill the first row with 9 unique random numbers.

2.Fill the rest of the spaces with zeroes(0).

3.Produce a random number and test the number to the sudoku rules .Columns, 3x3 grids and rows should have unique numbers from 1-9.

4. Repeat the process untill all zeroes are replaced by a number from 1-9.
The logic has some major flaws that are preventing the program from working perfectly.

Here's a general output screen: http://img693.imageshack.us/img693/3732/sudokuq.png

As you can see that those zeroes cannot be filled as the required number does not satisfy all the three rules.

Any help in improving my logic will be very much appreciated. I have attached a rough program in case you need to see the logic in C++ syntax.
Thanks a lot, in advance!

#include<iostream.h>
#include<conio.h>
#include<ctime>
#include<cstdlib>

int main()
{   int i,j,k,l,r,r2,s,m,o,z,p,q,x,flag1,flag2,flag3;   //declaration of variables               

    int A[9][9];                                        //Sudoku 9x9 Array
     
    srand(time(0));                                     //Initialize seed to system time
    
    int filled[9]={1,2,3,4,5,6,7,8,9};                  //filled array used to create 9 UNIQUE randome numbers
  
   //Assign sudoku row 1 to 9 unique numbers
      for(i=0;i<9;i++)                                 
        {replay:
              r=(rand()%9)+1;
         if(filled[r-1]==0)                            //No importance,initially. 
              goto replay;
        
         for(j=0;j<9;j++)
         {
          if(r==filled[j])
            {filled[j]=0;}
          }
        
            
        A[0][i]=r;
     
       
   
       }

//Assign all other 9x8=72 blanks, ZERO
for(i=1;i<9;i++)
  {for(j=0;j<9;j++)
      A[i][j]=0;
  }


s=1;
 while(s<=9)
{r2=s; 
 
 for(i=1;i<9;i++)

   {
   for(j=0;j<9;j++)
     {flag1=0;
      flag2=0;
      flag3=0;
      for(x=0;x<9;x++)
        {if(r2==A[x][j])
            {flag1=1;
              break;}
         
        }
     
     if(flag1!=1)
          {for(m=0;m<9;m++)
                {if(r2==A[i][m])
                      {flag3=1;break;}
                }
          
           if(flag3!=1)
                {if(i<=2)   //2.grid test
                     {if(j<=2)
                          {o=2;z=2;}
                      else if(j<=5)
                          {o=2;z=5;}
                      else if(j<=8)
                          {o=2;z=8;}
                      
                     }
                     
                 else if(i<=5)
                      {if(j<=2)
                          {o=5;z=2;}
                      else if(j<=5)
                          {o=5;z=5;}
                      else if(j<=8)
                          {o=5;z=8;}
                      
                     }
                     
                 else if(i<=8 && j<=8)
                      {if(j<=2)
                          {o=8;z=2;}
                      else if(j<=5)
                          {o=8;z=5;}
                      else if(j<=8)
                          {o=8;z=8;}
                      
                     }
                 }
              
                     
                 for(k=o; k>=o-2;k--)
                   {for(l=z;l>=z-2;l--)
                      if(r2==A[k][l])
                           {flag2=1;break;}
                   }
         
                if(flag2!=1 && A[i][j]==0)                  
                      A[i][j]=r2;
                
               }
         } 
      }
s++;
}    
   
 /*       
 for(p=0;p<9;p++)
   {for(q=0;q<9;q++)
      if(A[p][q]==0)
        goto replay2;
   }           
             
 */             



 
 
 //Display
 
 cout<<"  ";
 for(q=0;q<30;q++)
      {cout<<"-";}
 cout<<endl;
      
 for(p=0;p<9;p++)
   {cout<<" | ";
   if(p==3||p==6)
         cout<<"------------------------------"<<endl<<"   ";
   for(q=0;q<9;q++)
      {if(q==3 || q==6)
          {cout<<"| ";}
       cout<<A[p][q]<<"  ";
      }
    cout<<"\b\b|"<<endl<<endl;
   }        
  cout<<"  ";                 
  for(q=0;q<30;q++)
      {cout<<"-";}
 cout<<endl;              

       
getch();
}
  • 3 Contributors
  • 11 Replies
  • 6K Views
  • 1 Year Discussion Span
  • Latest Post Latest Post by alexanderlegend
Member Avatar for Taywin

The algorithm to produce a valid solution depends on how your data structure is going to be. Do you concern about the speed or space? Brute force would be the easiest way but not really good for this.

What you may need to think about could be as followed:
1)Start the square from the middle 9-square.
2)Keep in mind that creating a solution for sudoku is to find a correct path. In order to find a path, you need to be able to back track your path.
3)There should be another storage keeping track of what number you have tried to fill in and not get the result, or you may keep going in a loop when you do back tracking.

There are sudoku algorithms floating around the Internet as well. You may just google and look for one that suite you if you want to.

Member Avatar for nbaztec

Well this would just be my opinion.
1. Fill a Box 3x3
2. Move 2 Next Box's 1st column.
3. Create 3 arrays/vectors
___a. For that Box
___b. For Horizontal Line
___c. For Vertical Line
4. Select a random number & test to ensure it doesn't exist in any of the 3 arrays.
5. Repeat for all numbers in Box. Only b) & c) change.
6. Move to next box.

This would be my logic.

Edited by nbaztec because: n/a
Member Avatar for Taywin

4. Select a random number & test to ensure it doesn't exist in any of the 3 arrays.

This is where the problem occurs. What to do if there is no valid number can be found. I believe, his way to get away from being stuck is to fill in with '0'.

In his logic, the problem is that he starts from one square, and keep going to others. The latter the square he is trying to fill in, the more constraint to those squares are. Of course, the constraint will eventually cause the '0' result because there is no solution. Your logic is similar to his but taking a little bit different approach. It will always work if and only if there is a solution for every path.

Please keep in mind that you are working with a search algorithm. The result you need is to find the right path, not to test whether the path is valid. Because the result you need is more specific, it is not trivia.

Member Avatar for nbaztec

This is where the problem occurs. What to do if there is no valid number can be found.

It can't be possible. If that happens means there is something wrong with the Sudoku algorithm.

I believe, his way to get away from being stuck is to fill in with '0'.

No, that's just "emptying" of the board. 0 is not a valid number in Sudoku.

It will always work if and only if there is a solution for every path.

Yes in a Sudoku, there will always be a solution. I agree it won't hold good for other types of searches but I'm just making this Sudoku-specific Algorithm.

Member Avatar for Taywin

It can't be possible. If that happens means there is something wrong with the Sudoku algorithm.

No, that's just "emptying" of the board. 0 is not a valid number in Sudoku.

That's why the '0' is filled in his solution because it is impossible.

Yes in a Sudoku, there will always be a solution. I agree it won't hold good for other types of searches but I'm just making this Sudoku-specific Algorithm.

I think you are not on the same pace with me here. I do not disagree that a valid sudoku always has a solution, but that does not apply to a sudoku generator. In other words, a valid sudoku is only one of correct solutions generated by a sudoku generator, but there are tons of way to fill in those 81 slots and won't be a valid sudoku. A way of going straight forward (close to brute force) only won't always give a valid solution because eventually certain squares will have no value to fill in (1-9).

I am not sure how much the thread creator familiar with path finder algorithm. This is not a simple task in order to always generate a valid solution. You could, however, keep generating and disregard those invalid, and then spit out only valid solution. That is one way of doing so, but it does not guarantee the time of generating and it is pure brute force. To fix the problem at the cause, an algorithm that can backtrack what is being generated may be used (could be recursive but not recommended).

Edited by Taywin because: n/a
Member Avatar for alexanderlegend

I don't have any specific targets of speed. I just want the board to be filled as fast as possible. The program I wrote is not exactly a 100% failure. The number of zeroes keeps varying and very rarely, does a perfect board come up.
I am not familiar with path finder algorithm but I am reading about backtracking now.

Member Avatar for nbaztec

This is not a simple task in order to always generate a valid solution. You could, however, keep generating and disregard those invalid, and then spit out only valid solution. That is one way of doing so, but it does not guarantee the time of generating and it is pure brute force.

Agreed. Please, forgive me for over-seeing the fact that the constraints set upon by other values might lead to a totally invalid solution. Judging by this the OP should face some problems.
The only work-around I think is to generate say 500 Puzzles before hand and save them. It might take a lot of time for brute-force though but would prove to be a much better user experience.
Also the OP can use OOP & assign the board a ID so to prevent the loading of same puzzles within say last 100 games.

Edited by nbaztec because: n/a
Member Avatar for nbaztec

Well I think the re-clarified logic would be:

1. Fill a Box 3x3
2. Move 2 Next Box's 1st column.
3. Create 3 arrays/vectors
___a. For that Box
___b. For Horizontal Line
___c. For Vertical Line
4. Select a random number & test to ensure it doesn't exist in any of the 3 arrays.
if--> number exists in all 3 arrays. Trash it & start again. Goto Step 2.
else-->
5. Repeat for all numbers in Box. Only b) & c) change.
6. Move to next box.

Member Avatar for Taywin

Your solution would produce more valid result. :) However, I am sorry to tell you that this could cause a problem in an infinite loop even though the possibility is very low. Given a scenario when a box cannot be completely filled with 1-9 unique number using any combinations (from 9! possibilities), the program will keep going back to step 2 over and over again. As I stated earlier, it would be rare, but it is possible.

I have some ideas about how to do it, but I have no time to compose the thought in a write up... Sorry about that... :(

Edited by Taywin because: n/a
Member Avatar for nbaztec

Given a scenario when a box cannot be completely filled with 1-9 unique number using any combinations (from 9! possibilities), the program will keep going back to step 2 over and over again. As I stated earlier, it would be rare, but it is possible

I too agree on that. But I'd rather keep this inside a separate thread. :)
That ought to give it some boost.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.