This is a code in JAVA for solving the sudoku problem for any 9*9 sudoku grid using backtracking. It is not printing any output. I am not able to find the mistake in this. Please help. I have included one of the sample input int the main function in the form of a 9*9 grid. is_safe function if it is safe to put the selected character there by checking the same row, same column and the corresponding 3*3 grid. The base case checks when cr becomes 9, that is, reaches the end of board and cl becomes 0, that is, when we reach out of the board. Then a possible solution may have been found. We print the board at that point and return to the calling function. It seems logically correct but it is not printing any output.
public static boolean is_safe(int mat[][],int cr,int cl,int i)
{
for(int k=0;k<mat.length;k++)
{
if(k!=cl&&mat[cr][k]==i)
return false;
if(k!=cr&&mat[k][cl]==i)
return false;
}
int row=cr-cr%3;
int col=cl-cl%3;
for(int k=0;k<3;k++)
{
for(int l=0;l<3;l++)
{
if(mat[k+row][l+col]==i)
return false;
}
}
return true;
}
public static void print(int mat[][])
{
for(int i=0;i<mat.length;i++)
{
for(int j=0;j<mat[0].length;j++)
{
System.out.println(mat[i][j]);
}
System.out.println();
}
}
public static void func(int mat[][],int cr,int cl)
{
if(cr==mat.length&&cl==0)
{
print(mat);
return;
}
int i=cr,j=cl;
if(mat[cr][cl]!=0)
{
if(cl+1==9)
func(mat,cr+1,0);
else
func(mat,cr,cl+1);
}
else{
for(int k=1;k<=9;k++)
{
if(is_safe(mat,i,j,k))
{
mat[i][j]=k;
if(j+1==mat.length)
func(mat,i+1,0);
else
func(mat, i, j+1);
mat[i][j]=0;
}
}
}
}
public static void main(String[] args) {
int mat[][]={{3,0,6,5,0,8,4,0,0},
{5,2,0,0,0,0,0,0,0},
{0,8,7,0,0,0,0,3,1},
{0,0,3,0,1,0,0,8,0},
{9,0,0,8,6,3,0,1,5},
{0,5,0,0,9,0,6,0,0},
{1,3,0,0,0,0,2,5,0},
{0,0,0,0,0,0,0,7,4},
{0,0,5,2,0,6,3,0,0}};
func(mat,0,0);
}
}```
Your print method is never called! It seems that the sodoku is not solvable!
With the following input your code works fine:
{{3,0,6,5,0,8,4,0,0},
{5,2,0,0,0,0,0,0,0},
{0,8,7,0,0,0,0,3,1},
{0,0,3,0,1,0,0,8,0},
{9,0,0,8,6,3,0,0,5},
{0,5,0,0,9,0,6,0,0},
{1,3,0,0,0,0,2,5,0},
{0,0,0,0,0,0,0,7,4},
{0,0,5,2,0,6,3,0,0}};
You can also change your print method to make it more readable:
public static void print(int mat[][]) {
for (int i = 0; i < mat.length; i++) {
List<String> stringList = Arrays.stream(mat[i])
.mapToObj(String::valueOf).collect(Collectors.toList());
System.out.println(String.join(" ", stringList));
}
}
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9