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.
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
