Hi, I am going to explain to you how to make a sudoku puzzle generator in java. The algorithm followed by me is taken from Sudoku Algorithm. Though I will be explaining the code in detail it would be better if you read and understand the algorithm from the above-mentioned site.
Generating a valid: For a 9×9 grid to be a valid Sudoku grid, the following 3 requirements should be fulfilled:
- for each row: every number from 1 to 9 should occur exactly once
- for each column: every number from 1 to 9 should occur exactly once
- for each 3×3 square with a thicker border (there are 9 of them): every number from 1 to 9 should occur exactly once.
public static void generate()
{
int k=1,n=1;
for(int i=0;i<9;i++)
{
k=n;
for(int j=0;j<9;j++)
{
if(k<=9){
a[i][j]=k;
k++;
}else{
k=1;
a[i][j]=k;
k++;
}
}
n=k+3;
if(k==10)
n=4;
if(n>9)
n=(n%9)+1;
}
}
Generate random numbers to interchange rows and columns within a same group:
In this function, we select any two rows randomly from the same group and interchange it as shown in the figure. We select two rows from each of the three groups. Similarly, we do for columns.
public static void random_gen(int check){
int k1,k2,max=2,min=0;
Random r= new Random();
for(int i=0;i<3;i++)
{
//There are three groups.So we are using for loop three times.
k1=r.nextInt(max-min+1)+min;
//This while is just to ensure k1 is not equal to k2.
do{
k2=r.nextInt(max-min+1)+min;
}while(k1==k2);
max+=3;min+=3;
//check is global variable.
//We are calling random_gen two time from the main func.
//Once it will be called for columns and once for rows.
if(check==1)
//calling a function to interchange the selected rows.
permutation_row(k1,k2);
else if(check==0)
permutation_col(k1,k2);
}
}Interchange 2 rows and columns: Following functions will interchange two rows and two columns.
//For row
public static void permutation_row(int k1,int k2){
int temp;//k1 and k2 are two rows that we are selecting to interchange.
for(int j=0;j<9;j++)
{
temp=a[k1][j];
a[k1][j]=a[k2][j];
a[k2][j]=temp;
}
}//For column
public static void permutation_col(int k1,int k2){
int temp;
for(int j=0;j<9;j++)
{
temp=a[j][k1];
a[j][k1]=a[j][k2];
a[j][k2]=temp;
}
}Interchanging two groups of row and two groups of column:
The above picture is self-explanatory as to what are we doing now.
public static void row_change(int k1,int k2)
{
int temp;
for(int n=1;n<=3;n++)
{
for(int i=0;i<9;i++)
{
temp=a[k1][i];
a[k1][i]=a[k2][i];
a[k2][i]=temp;
}
k1++;
k2++;
}
}
public static void col_change(int k1,int k2)
{
int temp;
for(int n=1;n<=3;n++)
{
for(int i=0;i<9;i++)
{
temp=a[i][k1];
a[i][k1]=a[i][k2];
a[i][k2]=temp;
}
k1++;
k2++;
}
}
Striking out cells: After doing all kind of interchanging its time to strike out the elements from the cells. These interchangings were essential to randomize the matrix as far as possible.
To strike out the elements level1 check is used. To know more about level1 check go to the link given and read Step 3, 4th point.
public static void strike_out(int k1,int k2)
{
int row_from;
int row_to;
int col_from;
int col_to;
int i,j,b,c;
int rem1,rem2;
int flag;
int temp=a[k1][k2];
int count=9;
for(i=1;i<=9;i++)
{ flag=1;
for(j=0;j<9;j++)
{
if(j!=k2)
{
if(i!=a[k1][j])
{
continue;
}
else
{
flag=0;
break;
}
}
}
if(flag==1)
{
for(c=0;c<9;c++)
{
if(c!=k1)
{
if(i!=a[c][k2])
{
continue;
}
else
{
flag=0;
break;
}
}
}
}
if(flag==1)
{
rem1=k1%3; rem2=k2%3;
row_from=k1-rem1;
row_to=k1+(2-rem1);
col_from=k2-rem2;
col_to=k2+(2-rem2);
for(c=row_from;c<=row_to;c++)
{
for(b=col_from;b<=col_to;b++)
{
if(c!=k1 && b!=k2)
{
if(i!=a[c][b])
continue;
else{
flag=0;
break;
}
}
}
}
}
if(flag==0)
count--;
}
if(count==1)
{
a[k1][k2]=0;
counter_num--;
}
}
This function may look tough but its very easy to understand. If you are clear with level1 check it won’t take much time to understand this.
Main function:
public static void main(String[] args)throws IOException
{
BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
int counter=1,k1,k2;
generate();
random_gen(1);
random_gen(0);
System.out.println();
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
System.out.print(a[i][j]+"\t");
}
System.out.println("");
}
Random rand=new Random();
int n[]={0,3,6};
for(int i=0;i<2;i++)
{
k1=n[rand.nextInt(n.length)];
do{
k2=n[rand.nextInt(n.length)];
}while(k1==k2);
if(counter==1)
row_change(k1,k2);
else col_change(k1,k2);
counter++;
}
int max=8;
int min=0;
//Striking out
for(k1=0;k1<9;k1++)
{
for(k2=0;k2<9;k2++)
strike_out(k1,k2);
}
System.out.println();
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
System.out.print(a[i][j]+"\t");
}
System.out.println("");
}
}This is the complete code to create a sudoku puzzle generator. If you need any clarification on any topic you can ask in the comment box.
Coder's Caffeine 