Sudoku Solver

Problem Statement

Embark on a challenge to solve a 9×9 Sudoku puzzle! Given a partially filled grid, fill every empty cell (marked with '.') with digits 1-9 so that each row, column, and 3×3 subgrid contains all digits exactly once. This hard-level problem harnesses the power of backtracking to explore all possibilities—imagine being a detective piecing together a numeric masterpiece, ensuring no rule is broken!

Example

Input: A 9×9 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: Solved board (one possible solution):

[
 ["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"]
]
            

The output satisfies all Sudoku rules: no digit repeats in any row, column, or 3×3 subgrid.

Code

public class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, row, col, c)) {
                            board[row][col] = c;
                            if (solve(board)) return true;
                            board[row][col] = '.'; // Backtrack
                        }
                    }
                    return false; // No valid number found
                }
            }
        }
        return true; // Board is fully filled
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int x = 0; x < 9; x++) {
            // Check row, column, and 3x3 subgrid
            if (board[row][x] == c || board[x][col] == c || 
                board[row - row % 3 + x / 3][col - col % 3 + x % 3] == c) {
                return false;
            }
        }
        return true;
    }
}
            

def solve_sudoku(board):
    def solve():
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    for c in "123456789":
                        if is_valid(i, j, c):
                            board[i][j] = c
                            if solve():
                                return True
                            board[i][j] = "."  # Backtrack
                    return False  # No valid number found
        return True  # Board is fully filled
    
    def is_valid(row, col, c):
        for x in range(9):
            # Check row
            if board[row][x] == c:
                return False
            # Check column
            if board[x][col] == c:
                return False
            # Check 3x3 subgrid
            if board[3 * (row // 3) + x // 3][3 * (col // 3) + x % 3] == c:
                return False
        return True
    
    solve()
    return board  # Modified in-place

# Example usage (simplified for display)
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)
for row in board:
    print(row)  # Outputs the solved board
            

function solveSudoku(board) {
    function solve() {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === ".") {
                    for (let c = "1"; c <= "9"; c++) {
                        if (isValid(i, j, c)) {
                            board[i][j] = c;
                            if (solve()) return true;
                            board[i][j] = "."; // Backtrack
                        }
                    }
                    return false; // No valid number found
                }
            }
        }
        return true; // Board is fully filled
    }
    
    function isValid(row, col, c) {
        for (let x = 0; x < 9; x++) {
            // Check row
            if (board[row][x] === c) return false;
            // Check column
            if (board[x][col] === c) return false;
            // Check 3x3 subgrid
            if (board[Math.floor(row / 3) * 3 + Math.floor(x / 3)]
                    [Math.floor(col / 3) * 3 + x % 3] === c) return false;
        }
        return true;
    }
    
    solve();
    return board; // Modified in-place
}

// Example usage
const 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"]
];
solveSudoku(board);
console.log(board); // Outputs the solved board
            

Explanation

• Base Case: If the board is fully filled (no '.' remains), return true—puzzle solved!
• Backtracking: For each empty cell, try digits 1-9; if valid, place it and recurse.
• Validation: Check the row, column, and 3×3 subgrid for conflicts before placing a digit.
• Flow Example: Start at (0,2) → try '4' → valid → recurse → next empty → try '6', etc., backtracking if a path fails.
• In-Place: Modifies the board directly, undoing moves (replacing with '.') when a path dead-ends.
• Success: Stops at the first valid solution (Sudoku puzzles typically have one unique solution).

Note