# 37. Sudoku Solver LeetCode Solution

In this guide we will provide 37. Sudoku Solver LeetCode Solution with best time and space complexity. The solution to Sudoku Solver problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

## Table of Contents

- Problem Statement
- Sudoku Solver solution in C++
- Sudoku Solver soution in Java
- Sudoku Solver solution Python
- Additional Resources

## Problem Statement of Sudoku Solver

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 3×3 sub-boxes 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.

### Complexity Analysis

**Time Complexity:**NP-Complete**Space Complexity:**O(1)

## 37. Sudoku Solver LeetCode Solution in C++

```
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;
}
};
```

/* code provided by PROGIEZ */

## 37. 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;
}
}
```

// code provided by PROGIEZ

## 37. Sudoku Solver LeetCode Solution in Python

```
class Solution:
def solveSudoku(self, board: list[list[str]]) -> None:
def isValid(row: int, col: int, c: str) -> 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)
```

#code by PROGIEZ

## Additional Resources

- Explore all Leetcode problems solutions at Progiez here
- Explore all problems on Leetcode website here

Feel free to give suggestions! Contact Us