Sudoku Solver Leetcode Solution

In this post, we are going to solve the Sudoku Solver Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` subboxes of the grid.

The `'.'` character indicates empty cells.

Example 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:

```

Constraints:

• `board.length == 9`
• `board[i].length == 9`
• `board[i][j]` is a digit or `'.'`.
• It is guaranteed that the input board has only one solution.

Now, lets see the leetcode solution of Sudoku Solver Leetcode Solution.

Sudoku Solver Leetcode Solution in Python

```class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def isValid(row: int, col: int, c: chr) -> bool:
for i in range(9):
if board[i][col] == c or \
board[row][i] == c or \
board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
return False
return True

def solve(s: int) -> bool:
if s == 81:
return True

i = s // 9
j = s % 9

if board[i][j] != '.':
return solve(s + 1)

for c in string.digits[1:]:
if isValid(i, j, c):
board[i][j] = c
if solve(s + 1):
return True
board[i][j] = '.'

return False

solve(0)
```

Sudoku SolverLeetcode Solutionin CPP

```class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board, 0);
}

private:
bool solve(vector<vector<char>>& board, int s) {
if (s == 81)
return true;

const int i = s / 9;
const int j = s % 9;

if (board[i][j] != '.')
return solve(board, s + 1);

for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board, s + 1))
return true;
board[i][j] = '.';
}

return false;
}

bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
};
```

Sudoku Solver Leetcode Solution in Java

```class Solution {
public void solveSudoku(char[][] board) {
dfs(board, 0);
}

private boolean dfs(char[][] board, int s) {
if (s == 81)
return true;

final int i = s / 9;
final int j = s % 9;

if (board[i][j] != '.')
return dfs(board, s + 1);

for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (dfs(board, s + 1))
return true;
board[i][j] = '.';
}

return false;
}

private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
}
```

Note: This problem Sudoku Solver is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Count and Say

Sharing Is Caring