Sudoku Solver LeetCode Solution

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

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.
Sudoku Solver example 1
fig-1
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 example 1 solution
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)