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
Top comments (0)