Algorithm: Solve Sudoku
Buckle up your seats, here, we are going to solve a Sudoku with some loops, dfs search & Backtracking.
I hope everyone reading this blog have tried to solve Sudoku and felt how nice it is to finally reach up to a solution! I have been solving Sudoku from quite some time and it still amazes me.
So as an effort to better understand the Sudoku solving techniques, I came across an algorithm to solve it programatically. Following simple steps leads us to a solution.
Here is how we will try to come up to a solution:
- Loop over for each empty cells
- Try filling the cell with digit from 1–9
- Check if digit (with which we filled the cell) is valid
- Check if the cell row & column doesn’t have that digit
- Check 3*3 box doesn’t have that digit
But first lets look how the input data would look like:
If we convert this image data as array:
Input: board = [
["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]
];Here, empty cells are denoted as “.”. Final output should look like:
If we convert it to array:
Output: [
[“5”,”3",”4",”6",”7",”8",”9",”1",”2"],[“6”,”7",”2",”1",”9",”5",”3",”4",”8"],[“1”,”9",”8",”3",”4",”2",”5",”6",”7"],[“8”,”5",”9",”7",”6",”1",”4",”2",”3"],[“4”,”2",”6",”8",”5",”3",”7",”9",”1"],[“7”,”1",”3",”9",”2",”4",”8",”5",”6"],[“9”,”6",”1",”5",”3",”7",”2",”8",”4"],[“2”,”8",”7",”4",”1",”9",”6",”3",”5"],[“3”,”4",”5",”2",”8",”6",”1",”7",”9"]
];Solution
Lets tackle finding out if the new number (from 1–9) placed at an empty cell, is properly placed or valid. That part is easy, if the new number doesn’t collide with existing numbers in that particular row/column, as a guess/assumption, we can go ahead with this number at this particular cell. Then we can try with new number (1–9) at next empty cell.
The further we go, there are thin chances of number not colliding, and if the new number collides, our assumption was wrong, we go back to the initial assumption, back on our path (Backtracking).
Code
- Loop over each row & column and find not-empty cells
// loop over rows
for(let row = 0; row < n; row++){
// loop over cols
for(let col = 0; col < n; col++){
// if cell is already filled, skip it
if(board[row][col] != ".") continue;
}
}2. Check if the new cell value doesn’t collide with existing value. It consists of two checks, first: It shouldn’t collide with existing row & column values. second: It shouldn’t collide with 3*3 box’s existing values.
function isValid(board, row, col, n, newVal){
// get box row number
let boxRow = Math.floor(row/3) * 3;
// get box col number
let boxCol = Math.floor(col/3) * 3;
// loop over board length
for(let i = 0; i < n; i++){
// stop if the newVal collides with existing row/col values
if(board[row][i] == newVal || board[i][col] == newVal) return false;
// get current row
const curRow = boxRow + Math.floor(i/3);
// get current col
const curCol = boxCol + Math.floor(i%3);
// stop if the newVal collides with 3*3 box values
if(board[curRow][curCol] == newVal) return false;
}
return true;
}3. If our assumption is right, we can place this newVal to out decided cell & move to the next empty cell. And if the assumption is wrong (newVal collides with existing rows/cols/box values), we can mark the cell as empty again.
// try every number from 1-9
for(let i = 1; i <= 9; i++){
const c = i.toString();
// if that is a valid
if(isValid(board, row, col, n, c)){
board[row][col] = c;
// the number is valid, continue with next assumption
if(dfs(board, n)) return true;
}
}
// valid number couldn't be found
// set it back to "."
board[row][col] = ".";Complete Code
We understood entire process using code chunks. Now is the time to merge the code chunks into a single code block. Here it is:
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/var solveSudoku = function(board) {
const n = board.length;
dfs(board, n);
};function dfs(board, n){
// loop over rows
for(let row = 0; row < n; row++){
// loop over cols
for(let col = 0; col < n; col++){
// if cell is already filled, skip it
if(board[row][col] != ".") continue;
// try every number from 1-9
for(let i = 1; i <= 9; i++){
const c = i.toString();
// if that is a valid number
if(isValid(board, row, col, n, c)){
board[row][col] = c;
if(dfs(board, n)) return true;
}
}
// the number couldn't be found
// set it back to "."
board[row][col] = ".";
// return false to signal dead end
return false;
}
}
// all cells filled, must be a solution
return true;
}function isValid(board, row, col, n, newVal){
// get box row number
let boxRow = Math.floor(row/3) * 3;
// get box col number
let boxCol = Math.floor(col/3) * 3;
// loop over board length
for(let i = 0; i < n; i++){
// stop if the newVal collides with existing row/col values
if(board[row][i] == newVal || board[i][col] == newVal) return false;
// get current row
const curRow = boxRow + Math.floor(i/3);
// get current col
const curCol = boxCol + Math.floor(i%3);
// stop if the newVal collides with 3*3 box values
if(board[curRow][curCol] == newVal) return false;
}
return true;
}
Now we can call the method solveSudoku(input), and it will fill the input variable with correct data, and if actual solution is not possible, it will not modify the variable at all.
I hope everyone reading this learnt something about Backtracking, DFS, and some concepts about algorithm.
If you wont to learn more about Programming, Backend engineering, follow me on Medium and also on twitter also. See you in next article!
