Soduku (Backtracking )- GFG

Given an incomplete Sudoku configuration in terms of a 9 x 9 2-D square matrix (grid[][]), the task to find a solved Sudoku. For simplicity, you may assume that there will be only one unique solution.

Input:
grid[][] = 
[[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]]
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

Expected Time Complexity: O(9N*N).
Expected Auxiliary Space: O(N*N).

Java Solution :-

class Solution
{
public static final int size=9;

static Boolean solve(int grid[][], int row, int col) {

if (row == size)
return true;

int newRow, newCol;
if (col == size — 1) {
newRow = row + 1;
newCol = 0;
} else {
newRow = row;
newCol = col + 1;
}

if (grid[row][col] > 0)
return solve(grid, newRow, newCol);

for (int num = 1; num < 10; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if(solve(grid, newRow, newCol))
return true;
grid[row][col] = 0;
}
}
return false;
}

static Boolean isSafe(int grid[][], int row, int col, int val) {

for (int c = 0; c < size; c++) {
if (grid[row][c] == val)
return false;
}

for (int r = 0; r < size; r++) {
if (grid[r][col] == val)
return false;
}

int subMatrixRow = row / 3 * 3;
int subMatrixCol = col / 3 * 3;

for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (grid[r + subMatrixRow][c + subMatrixCol] == val)
return false;
}
}

return true;
}


static boolean SolveSudoku(int grid[][])
{

return solve(grid, 0, 0);
}


static void printGrid (int grid[][])
{
for (int r = 0; r < size; r++) {
for (int c = 0; c < size; c++)
System.out.print(grid[r][c] + “ “);
}
}
}