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) {
  // your code goes here
};

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