Here, We see Sudoku Solver problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
Sudoku Solver LeetCode Solution
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)
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] = '.';
}
}
};
Code language: C++ (cpp)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;
}
}
}
Code language: Java (java)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
};
Code language: JavaScript (javascript)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
Code language: Python (python)Min Stack LeetCode Solution
Design a stack that supports push, pop, top, and retrieving the minimum element in constant…
Find First and Last Position of Element in Sorted Array LeetCode Solution
Given an array of integers nums sorted in non-decreasing order, find the starting and ending…
Pow(x n) LeetCode Solution
Implement pow(x, n), which calculates x raised to the power n.
Group Anagrams LeetCode Solution
Given an array of strings strs, group the anagrams together. You can return the answer…
Rotate Image LeetCode Solution
You are given an n x n 2D matrix representing an image, rotate the image…
Permutations II LeetCode Solution
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in…