# Solution For Sudoku Solver

The Sudoku Solver problem on LeetCode is a classic backtracking problem, where we are supposed to find a solution for a given Sudoku board. The problem statement requires us to fill the board with numbers from 1 to 9, such that each row, column, and 3 x 3 sub-grid contains all the numbers from 1 to 9.

The suggested approach is to use backtracking to place a number in the empty cells of the Sudoku board, and to keep checking if the number satisfies the constraints of the game. The given Sudoku board can have multiple solutions, and we need to find all of them.

Let us first discuss the algorithm for solving this problem:

Algorithm:

• Define a function called `solveSudoku` that takes the initial Sudoku board as input and returns the solved board.
• Create a helper function `isValid` to check the validity of the number in a particular position of the board.
• Iterate through each cell of the board.
• If the cell is empty, iterate from 1 to 9 and try placing each number in the cell.
• Check if the number placed in the cell is valid by calling the `isValid` method.
• If the number is valid, recursively fill the rest of the board using the same approach until the board is completely filled.
• If the placement of the number leads to an invalid board, then backtrack and try the next number.
• If all the numbers from 1 to 9 have been tried and no number leads to a valid solution, then backtrack to the previous cell and try the next number from there.
• If there are no empty cells left on the board and the board satisfies all the constraints, then we have found a valid solution.

Now, let us implement the above algorithm in Python.

“`
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
“””
Do not return anything, modify board in-place instead.
“””
def isValid(row, col, num):
# Check if num already exists in row
for i in range(9):
if board[row][i] == num:
return False
# Check if num already exists in column
for i in range(9):
if board[i][col] == num:
return False
# Check if num already exists in 3×3 sub-grid
row_start = (row // 3) * 3
col_start = (col // 3) * 3
for i in range(row_start, row_start + 3):
for j in range(col_start, col_start + 3):
if board[i][j] == num:
return False
return True

``````    def solve():
for row in range(9):
for col in range(9):
if board[row][col] == '.':
for num in range(1, 10):
if isValid(row, col, str(num)):
board[row][col] = str(num)
if solve():
return True
board[row][col] = '.'
return False
return True

solve()
``````

“`

Let us go through the code snippet step by step.

• We define a function `isValid` that takes the row, column, and number as input, and checks if the placement of the given number is valid in that cell.
• We define the `solve` function that iterates through all cells of the board, and tries to fill the empty cells with numbers from 1 to 9.
• We use recursion to fill the rest of the board using the same approach until the board is completely filled.
• We use backtracking to undo the previous placement of the number if it does not lead to a valid solution.
• Finally, we call the `solve` function to solve the Sudoku board.

The time complexity of this algorithm is O(9^(nn)), where n is the side of the board, which is typically 9. The space complexity is O(nn).

In conclusion, we have discussed the approach to solve the Sudoku Solver problem on LeetCode using backtracking. The above solution allows us to find all the possible solutions of the given Sudoku board.

## Step by Step Implementation For Sudoku Solver

```public class Solution {
public void solveSudoku(char[][] board) {

// we use a helper function isValid to check if a given number
// can be placed at a given row and column in the sudoku board
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){
if(isValid(board, i, j, c)){
board[i][j] = c;

// if we were able to successfully place a number
// at a given row and column, we recursively call
// the solveSudoku function to see if we can
// solve the rest of the sudoku
if(solveSudoku(board))
return;
else
board[i][j] = '.';
}
}

// if we tried all numbers for the given row and column
// and still couldn't solve the sudoku, that means the
// sudoku is unsolvable, so we return false
return false;
}
}
}

// if we reach this point, that means we were able to successfully
// place all numbers in the sudoku, so we return true
return true;
}

public boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}```
```def solveSudoku(board):
# Base case - if the board is full, we're done
if not any("." in row for row in board):
return True

# Choose an empty cell
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == ".":
# Try every number from 1-9 in this cell
for k in range(1, 10):
board[i][j] = str(k)
# If this number works, keep going
if isValid(board, i, j) and solveSudoku(board):
return True
# Otherwise go back and try another number
board[i][j] = "."
# If we've tried every number and none worked,
# this is not a valid Sudoku
return False

# Check if a given board is valid
def isValid(board, i, j):
# Check row
for k in range(len(board)):
if k != j and board[i][k] == board[i][j]:
return False

# Check column
for k in range(len(board)):
if k != i and board[k][j] == board[i][j]:
return False

# Check 3x3 subgrid
box_x = (i // 3) * 3
box_y = (j // 3) * 3
for k in range(3):
for l in range(3):
if box_x + k != i and box_y + l != j and board[box_x + k][box_y + l] == board[i][j]:
return False

# Everything checked out!
return True```
```var sudoku = function(board) {
};```
```class Solution {
public:
void solveSudoku(vector>& board) {

// check if the board is valid
if(!isValid(board))
return;

// find an empty cell
int row, col;
if(!findEmptyCell(board, row, col))
return;

// try to fill the cell with a digit from 1 to 9
for(int num = 1; num <= 9; num++){

// if the digit is valid in the cell, fill it and recurse
if(isValid(board, row, col, num)){
board[row][col] = num + '0';

if(solveSudoku(board))
return;

// if the digit is not valid, reset the cell to empty
board[row][col] = '.';
}
}

return;
}

// check if the board is valid
bool isValid(vector>& board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] != '.' && !isValid(board, i, j, board[i][j] - '0'))
return false;
}
}
return true;
}

// check if the cell is valid
bool isValid(vector>& board, int row, int col, int num){

// check if the number is valid in the row
for(int i = 0; i < 9; i++){
if(board[row][i] == num + '0')
return false;
}

// check if the number is valid in the column
for(int i = 0; i < 9; i++){
if(board[i][col] == num + '0')
return false;
}

// check if the number is valid in the 3x3 sub-board
int subRow = row - row % 3;
int subCol = col - col % 3;

for(int i = subRow; i < subRow + 3; i++){
for(int j = subCol; j < subCol + 3; j++){
if(board[i][j] == num + '0')
return false;
}
}

return true;
}

// find an empty cell in the board
bool findEmptyCell(vector>& board, int& row, int& col){
for(row = 0; row < 9; row++){
for(col = 0; col < 9; col++){
if(board[row][col] == '.')
return true;
}
}
return false;
}
};```
```public class Solution {
public void SolveSudoku(char[][] board) {
Solve(board);
}

private bool Solve(char[][] board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//try every possible number
if(IsValid(board, i, j, c)){
board[i][j] = c; //put c for this cell

if(Solve(board))
return true; //if it's the solution return true
else
board[i][j] = '.'; //otherwise go back
}
}

return false;
}
}
}
return true;
}

private bool IsValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]