Last updated on October 10th, 2024 at 02:04 am
Here, We see Sudoku Solver LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
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
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)
1. Sudoku Solver Leetcode Solution 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] = '.';
}
}
};2. Sudoku Solver Leetcode Solution 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. Sudoku Solver Leetcode Solution 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
};4. Sudoku Solver Leetcode Solution 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