Last updated on January 20th, 2025 at 04:13 am
Here, we see the Sudoku Solver LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Backtracking, Hash Table, Matrix
Companies
Snapchat, Uber
Level of Question
Hard
Sudoku Solver LeetCode Solution
Table of Contents
1. Problem Statement
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.
Example 1: (fig-1) 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"]] 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"]] Explanation: The input board is shown above and the only valid solution is shown below: (fig-2)
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves searching through all possible combinations to solve a problem. It is particularly useful for constraint satisfaction problems like Sudoku, where we explore potential solutions and backtrack when a solution path is invalid.
3. Code Implementation in Different Languages
3.1 Sudoku Solver C++
class Solution {
public:
bool col[10][10],row[10][10],f[10][10];
bool flag = false;
void solveSudoku(vector<vector<char>>& board) {
memset(col,false,sizeof(col));
memset(row,false,sizeof(row));
memset(f,false,sizeof(f));
for(int i = 0; i < 9;i++){
for(int j = 0; j < 9;j++){
if(board[i][j] == '.') continue;
int temp = 3*(i/3)+j/3;
int num = board[i][j]-'0';
col[j][num] = row[i][num] = f[temp][num] = true;
}
}
dfs(board,0,0);
}
void dfs(vector<vector<char>>& board,int i,int j){
if(flag == true) return ;
if(i >= 9){
flag = true;
return ;
}
if(board[i][j] != '.'){
if(j < 8) dfs(board,i,j+1);
else dfs(board,i+1,0);
if(flag) return;
}
else{
int temp = 3*(i/3)+j/3;
for(int n = 1; n <= 9; n++){
if(!col[j][n] && !row[i][n] && !f[temp][n]){
board[i][j] = n + '0';
col[j][n] = row[i][n] = f[temp][n] = true;
if(j < 8) dfs(board,i,j+1);
else dfs(board,i+1,0);
col[j][n] = row[i][n] = f[temp][n] = false;
if(flag) return;
}
}
board[i][j] = '.';
}
}
};
3.2 Sudoku Solver Java
class Solution {
public void solveSudoku(char[][] board) {
dfs(board,0);
}
private boolean dfs(char[][] board, int d) {
if (d==81) return true; //found solution
int i=d/9, j=d%9;
if (board[i][j]!='.') return dfs(board,d+1);//prefill number skip
boolean[] flag=new boolean[10];
validate(board,i,j,flag);
for (int k=1; k<=9; k++) {
if (flag[k]) {
board[i][j]=(char)('0'+k);
if (dfs(board,d+1)) return true;
}
}
board[i][j]='.'; //if can not solve, in the wrong path, change back to '.' and out
return false;
}
private void validate(char[][] board, int i, int j, boolean[] flag) {
Arrays.fill(flag,true);
for (int k=0; k<9; k++) {
if (board[i][k]!='.') flag[board[i][k]-'0']=false;
if (board[k][j]!='.') flag[board[k][j]-'0']=false;
int r=i/3*3+k/3;
int c=j/3*3+k%3;
if (board[r][c]!='.') flag[board[r][c]-'0']=false;
}
}
}
3.3 Sudoku Solver JavaScript
var solveSudoku = function(board) {
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board.length; j++) {
if (board[i][j] === '.') {
for (let l = 1; l < 10; l++) {
if (isValid(board, i, j, l.toString())) {
board[i][j] = l.toString()
let solved = solveSudoku(board)
if (solved !== false) return solved
board[i][j] = '.'
}
}
return false
}
}
}
return board
};
function isValid(board, i, j, l) {
for (let p = 0; p < board.length; p++) {
if (board[i][p] === l) return false
if (board[p][j] === l) return false
let gridVal = board[3 * Math.floor(i/3) + Math.floor(p/3)][3 * Math.floor(j/3) + p % 3]
// 3 * Math.floor(i/3) and 3 * Math.floor(j/3) are the coordinates for
// the top-left square of the 3x3 grid that the value is in
if (gridVal === l) return false
}
return true
};
3.4 Sudoku Solver Python
class Solution(object):
def solveSudoku(self, board):
self.board = board
self.val = self.PossibleVals()
self.Solver()
def PossibleVals(self):
a = "123456789"
d, val = {}, {}
for i in xrange(9):
for j in xrange(9):
ele = self.board[i][j]
if ele != ".":
d[("r", i)] = d.get(("r", i), []) + [ele]
d[("c", j)] = d.get(("c", j), []) + [ele]
d[(i//3, j//3)] = d.get((i//3, j//3), []) + [ele]
else:
val[(i,j)] = []
for (i,j) in val.keys():
inval = d.get(("r",i),[])+d.get(("c",j),[])+d.get((i/3,j/3),[])
val[(i,j)] = [n for n in a if n not in inval ]
return val
def Solver(self):
if len(self.val)==0:
return True
kee = min(self.val.keys(), key=lambda x: len(self.val[x]))
nums = self.val[kee]
for n in nums:
update = {kee:self.val[kee]}
if self.ValidOne(n, kee, update): # valid choice
if self.Solver(): # keep solving
return True
self.undo(kee, update) # invalid choice or didn't solve it => undo
return False
def ValidOne(self, n, kee, update):
self.board[kee[0]][kee[1]] = n
del self.val[kee]
i, j = kee
for ind in self.val.keys():
if n in self.val[ind]:
if ind[0]==i or ind[1]==j or (ind[0]/3,ind[1]/3)==(i/3,j/3):
update[ind] = n
self.val[ind].remove(n)
if len(self.val[ind])==0:
return False
return True
def undo(self, kee, update):
self.board[kee[0]][kee[1]]="."
for k in update:
if k not in self.val:
self.val[k]= update[k]
else:
self.val[k].append(update[k])
return None
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(9n) | O(n) |
| Java | O(9n) | O(n) |
| JavaScript | O(9n) | O(n) |
| Python | O(9n) | O(n) |
where n is the number of empty cells.
- All implementations follow the same backtracking approach, with slight variations in how constraints are tracked.
- The time complexity is exponential due to the nature of backtracking, but this is acceptable for a 9×9 Sudoku board with a limited number of empty cells.
- The space complexity is linear with respect to the number of empty cells, as the recursion stack grows with the depth of the search tree.