Sudoku Solver, power of backtracking. 🔥
Akhil
Posted on April 17, 2020
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
Posted on April 17, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.