Sudoku Solver, power of backtracking. 🔥

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.

So you're given a grid :

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 ? ✔️

Simulating it :

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