Sudoku Solver

                                            
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    
    bool solve(vector<vector<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++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
};

                                            
class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        solve(board);
    }
    
    private boolean 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++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            
                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
}

                                            
class Solution(object):
    def solveSudoku(self, board):
        def is_valid(row, col, num):
            for i in range(9):
                if board[row][i] == num or board[i][col] == num:
                    return False
            startRow, startCol = 3 * (row // 3), 3 * (col // 3)
            for i in range(3):
                for j in range(3):
                    if board[i + startRow][j + startCol] == num:
                        return False
            return True
        
        def solve():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in map(str, range(1, 10)):
                            if is_valid(i, j, num):
                                board[i][j] = num
                                if solve():
                                    return True
                                board[i][j] = '.'
                        return False
            return True
        
        solve()

                                            
bool isSafe(char** board, int row, int col, char num) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) return false;
        if (board[i][col] == num) return false;
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false;
    }
    return true;
}

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++) {
                    if (isSafe(board, i, j, c)) {
                        board[i][j] = c;
                        if (solve(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

void solveSudoku(char** board, int boardSize, int* boardColSize) {
    solve(board);
}

                                            
public class Solution {
    public void SolveSudoku(char[][] board) {
        if(board == null || board.Length == 0) return;
        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++) {
                        if(isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if(Solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    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] == c) return false;
            if(board[row][i] == c) return false;
            if(board[3*(row/3) + i/3][3*(col/3) + i%3] == c) return false;
        }
        return true;
    }
}

                                            
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place 
instead.
 */
var solveSudoku = function(board) {
    const solve = () => {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === '.') {
                    for (let num = 1; num <= 9; num++) {
                        if (isValid(i, j, num.toString())) {
                            board[i][j] = num.toString();
                            if (solve()) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    };

    const isValid = (row, col, num) => {
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === num) return false;
            if (board[row][i] === num) return false;
            if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + i % 3] === num) return false;
        }
        return true;
    };

    solve();
};

                                            
/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    const solve = (): boolean => {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === '.') {
                    for (let num = 1; num <= 9; num++) {
                        const numStr = num.toString();
                        if (isValid(i, j, numStr)) {
                            board[i][j] = numStr;
                            if (solve()) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    };

    const isValid = (row: number, col: number, num: string): boolean => {
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === num || board[row][i] === num) {
                return false;
            }
            const startRow = 3 * Math.floor(row / 3);
            const startCol = 3 * Math.floor(col / 3);
            for (let i = 0; i < 3; i++) {
                for (let j = 0; j < 3; j++) {
                    if (board[startRow + i][startCol + j] === num) {
                        return false;
                    }
                }
            }
        }
        return true;
    };

    solve();
};

                                            
class Solution {
    func solveSudoku(_ board: inout [[Character]]) {
        func solve(_ board: inout [[Character]]) -> Bool {
            for i in 0..<9 {
                for j in 0..<9 {
                    if board[i][j] == "." {
                        for num in 1...9 {
                            let char = Character(String(num))
                            if isValid(board, i, j, char) {
                                board[i][j] = char
                                if solve(&board) {
                                    return true
                                } else {
                                    board[i][j] = "."
                                }
                            }
                        }
                        return false
                    }
                }
            }
            return true
        }

        func isValid(_ board: [[Character]], _ row: Int, _ col: Int, _ char: Character) -> Bool {
            for i in 0..<9 {
                if board[row][i] == char || board[i][col] == char || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == char {
                    return false
                }
            }
            return true
        }

        solve(&board)
    }
}

                                            
class Solution {
    fun solveSudoku(board: Array<CharArray>): Unit {
        fun isValid(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
            for (i in 0 until 9) {
                if (board[row][i] == num || board[i][col] == num || 
                    board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
                    return false
                }
            }
            return true
        }
        
        fun solve(): Boolean {
            for (i in 0 until 9) {
                for (j in 0 until 9) {
                    if (board[i][j] == '.') {
                        for (num in '1'..'9') {
                            if (isValid(board, i, j, num)) {
                                board[i][j] = num
                                if (solve()) {
                                    return true
                                }
                                board[i][j] = '.'
                            }
                        }
                        return false
                    }
                }
            }
            return true
        }
        
        solve()
    }
}

                                            
class Solution {
  void solveSudoku(List<List<String>> board) {
    if (board == null || board.isEmpty) return;
    
    _solve(board);
  }
  
  bool _solve(List<List<String>> board) {
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] == '.') {
          for (int k = 1; k <= 9; k++) {
            String c = k.toString();
            if (_isValidMove(board, i, j, c)) {
              board[i][j] = c;
              if (_solve(board)) {
                return true;
              } else {
                board[i][j] = '.';
              }
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  
  bool _isValidMove(List<List<String>> board, int row, int col, String c) {
    for (int i = 0; i < 9; i++) {
      if (board[row][i] == c) return false;
      if (board[i][col] == c) return false;
      if (board[3 * (row ~/ 3) + i ~/ 3][3 * (col ~/ 3) + i % 3] == c) return false;
    }
    return true;
  }
}

                                            
func solveSudoku(board [][]byte)  {
    solve(board)
}

func solve(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                for num := byte('1'); num <= byte('9'); num++ {
                    if isValid(board, i, j, num) {
                        board[i][j] = num
                        if solve(board) {
                            return true
                        } else {
                            board[i][j] = '.'
                        }
                    }
                }
                return false
            }
        }
    }
    return true
}

func isValid(board [][]byte, row, col int, num byte) bool {
    for i := 0; i < 9; i++ {
        if board[i][col] == num || board[row][i] == num || board[3*(row/3)+i/3][3*(col/3)+i%3] == num {
            return false
        }
    }
    return true
}

                                            
# @param {Character[][]} board
# @return {Void} Do not return anything, modify board in-place instead.
def solve_sudoku(board)
    def solve(board)
        (0..8).each do |i|
            (0..8).each do |j|
                if board[i][j] == "."
                    (1..9).each do |k|
                        if is_valid(board, i, j, k.to_s)
                            board[i][j] = k.to_s
                            if solve(board) 
                                return true
                            end
                            board[i][j] = "."
                        end
                    end
                    return false
                end
            end
        end
        return true
    end

    def is_valid(board, row, col, num)
        (0..8).each do |i|
            return false if board[i][col] == num || board[row][i] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num
        end
        true
    end

    solve(board)
end

                                            
impl Solution {
    pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
        fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, num: char) -> bool {
            for i in 0..9 {
                if board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num {
                    return false;
                }
            }
            true
        }
        
        fn solve(board: &mut Vec<Vec<char>>) -> bool {
            for i in 0..9 {
                for j in 0..9 {
                    if board[i][j] == '.' {
                        for num in (b'1'..=b'9').map(char::from) {
                            if is_valid(board, i, j, num) {
                                board[i][j] = num;
                                if solve(board) {
                                    return true;
                                }
                                board[i][j] = '.';
                            }
                        }
                        return false;
                    }
                }
            }
            true
        }
        
        solve(board);
    }
}

To solve this coding challenge of a Sudoku Solver, we need to create a program that can fill in the empty cells of a given 9x9 Sudoku board while adhering to the game's rules. Specifically, the rules state that each digit from 1 to 9 must appear exactly once in each row, column, and the three-by-three sub-boxes of the grid.

Explanation

Step-by-Step Logic:

Input Representation:

The board is a 2D list where each sub-list represents a row of the Sudoku. Empty cells are represented by the character
'.'

.

Validation Function:

We need a function to check if placing a particular number in a cell is valid. This involves three checks:

Row Check: The number should not already exist in the current row.
Column Check: The number should not already exist in the current column.
Sub-box Check: The number should not already exist in the current 3x3 sub-box.

The 3x3 sub-box can be determined using integer division and modulus operations.

Recursive Backtracking:

Use a recursive approach to attempt to place numbers in each empty cell. If placing the number leads to a valid solution, we proceed. If not, we backtrack and try the next number.
For each cell, iterate through digits '1' to '9', and use the validation function to check if the digit placement is valid.
Place the digit temporarily and recursively attempt to solve the remainder of the board.
If hitting a dead-end, reset the cell and backtrack to try the next available number.

End Condition:

When there are no more empty cells without contradictions, the board is successfully solved.

Detailed Steps in Pseudocode

                                            
# Pseudocode for Sudoku Solver

# Function to determine if placing 'num' at board[row][col] is valid
function is_valid(board, row, col, num):
    # Check if 'num' is already in the current row
    for i from 0 to 8:
        if board[row][i] == num:
            return False
    
    # Check if 'num' is already in the current column
    for i from 0 to 8:
        if board[i][col] == num:
            return False

    # Determine the starting indices of the 3x3 sub-box
    startRow = (row // 3) * 3
    startCol = (col // 3) * 3
    # Check if 'num' is already in the 3x3 sub-box
    for i from 0 to 2:
        for j from 0 to 2:
            if board[startRow + i][startCol + j] == num:
                return False
                
    # If all checks passed, it's valid to place 'num' at board[row][col]
    return True

# Main function to solve the Sudoku board using recursion and backtracking
function solve_sudoku(board):
    # Recursive helper function that attempts to solve the board
    function solve():
        # Iterate over each cell in the board
        for i from 0 to 8:
            for j from 0 to 8:
                # If cell is empty, try placing each digit from '1' to '9'
                if board[i][j] == '.':
                    for num in '123456789':
                        # Check if placing 'num' is valid
                        if is_valid(board, i, j, num):
                            # Temporarily place 'num' in the cell
                            board[i][j] = num
                            # Recursively attempt to solve the rest of the board
                            if solve():
                                return True
                            # Backtrack: revert the cell to empty if dead-end is reached
                            board[i][j] = '.'

                    # If no digits solve the board from this state, return False
                    return False
                    
        # If every cell is filled correctly, return True
        return True

    # Initiate the solving process
    solve()

# Example usage
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"]]

solve_sudoku(board)

# After running the function, the 'board' will be modified to the solved state.

By adhering to this step-by-step process and the respective pseudocode, we ensure the Sudoku grid is correctly filled, respecting all the rules intrinsic to a valid Sudoku solution. Recursive backtracking provides a straightforward method to explore all potential configurations systematically, guaranteeing a solution when feasible.