A while ago, I was developing a **sudoku game** as my side project, one of the functionalities I wanted to add in my app was ** one-click instant solution**.

### What the heck is sudoku?

Sudoku is a logic-based puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9.

and you've to fill it while maintaining relevant constraints. Solution:

### Thinking process

For each cell, we've to satisfy the following conditions:

1> Entry must be between integers 1 - 9.

2> The integer shouldn't match any other cell in it's column.

3> The integer shouldn't match any other cell in it's row.

4> The integer shouldn't match any other cell in 3x3 grid.

Let's start by solving this grid :

based on the input let's assume our input is :

```
grid[][] =
[
[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,3,0,0,6,0,0,0,3],
[4,3,0,8,0,3,0,0,1],
[7,3,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,0,0]
]
```

#### Let's go through it step by step

Go to the first empty cell.

Step 1> add a number between 1 - 9. Let's pick 1.

Step 2> check if it's valid for row ? ✔️ column ? ✔️ gird ? ✔️

by grid I mean :

```
[
[5,3,0],
[6,0,0],
[0,9,8]
]
```

Now let's move to the next cell and repeat the same process.

Step 1> add a number between 1 - 9. pick 1.

Step 2> check if it's valid for row ? ❌.

Step 3> Since not valid, move to the next number, pick 2.

Repeat Step 2> check if its a valid row ? ✔️ column ? ✔️ grid ? ✔️

Few things happened here :

1> at cell 7, 8 was placed instead of 6 because another 6 was in the same grid.

2> at cell 8, 9 was placed instead of 6 because another 6 was in the same column.

3> at cell 9, we wern't able to place 6 because of 6 being in the same grid.

So we've reached the end of row 1, and the last cell is empty and we can't place any integer between 1 - 9, so be backtrack.

4> at cell 8, we can't increase the number to 10, so be backtrack.

5> at cell 7, we place 9.

6> at cell 8, we can't place 6 or 8, we backtrack.

7> at cell 7, we're already at 9, no further values possible so backtrack.

8> at cell 6, we place 6 and continue doing the whole process.

Simulating the wholee process :

Let's write some code :

```
class Solution {
public void solveSudoku(int[][] board) {
solve(board);
}
public boolean solve(int[][] board){
// iterate through board and find the first empty cell
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
//if empty cell is found process it
if(board[i][j] == 0){
// try all combinations from 1 - 9
for(int c = 1;c<=9;c++){
// check if the current value of c satisfies all the conditions
if(isValid(board,i,j,c)){
// if it satisfies, then set the empty cell to that integer
board[i][j] = c;
// here we recursively call the solve method again.
// this leads to storing of current variables on to call stack
// for eg: at step 5> in cell 7, we place 9
//call stack : [5,3,1,2,7,4,9,0,0]
// but for next cell we couldn't place 6 or 8 in next cell.
// so we pop the call stack
// we cant change value of cell 7 since it's already at 9.
// we pop the call stack and change 2 -> 4 (Note: we can't change 7 )
// call stack : [5,3,1,4,7,0,0,0,0]
// this process continues
if(solve(board)){
return true;
}else{
// while recursing, if at some point we meet a condition which isn't satisfied
// and we end up back in current call stack, set the cell back to empty cell
// and try with next integer
board[i][j] = 0;
}
}
}
// if all the integers from 1 - 9 doesn't satisfy then return false
return false;
}
}
}
// if all conditions are satisfied return true;
return true;
}
//here we use bit of math
public boolean isValid(int[][] board,int row,int col,int c){
// we chose to go from 0 - 9 since
// each column has 9 cells
// each row has 9 cells
// and we need to check for each 3x3 gird and 3*3 = 9
for(int i=0;i<9;i++){
// check for each cell in column,
//if they're same then return false ie we found a duplicate
if(board[i][col] != 0 && board[i][col] == c) return false;
// check for rows
if(board[row][i] != 0 && board[row][i] == c) return false;
// check for each grid
// each grid is 3X3,
// grid 1:
// [0,0][0,1][0,2]
// [1,0][1,1][1,2]
// [2,0][2,1][2,2]
// grid 2:
// [0,3][0,4][0,5]
// [1,3][1,4][1,5]
// [2,3][2,4][2,5]..
// if we choose row = 2 and column = 4 we want
// row values between 0 - 2
// column values between 3 - 5
// for checking the grid and we have 9 values for i
// eg for i = 4, we want cell at [1,4]
// since row has to in between 0 - 2, and column in between 3 -5
// row equation : 3 * (row / 3) + i / 3
// column equation : 3 * (col/3) + i % 3
// for i = 4, row = 3*(1/3)+4/3 == 3*(0) + 1 = 1
// col = 3*(4/3)+4%3 == 3*(1) + 1 = 4
if(board[3*(row/3)+i/3][3*(col/3)+i%3] != 0 &&
board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
}
return true;
}
}
```

That's it ! except the bit of math, rest is easy.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/sudokuSolver.js

## Discussion (0)