Backtracking - Sudoku Solver

Write a program to solve a Sudoku puzzle by filling in the empty cells (represented as '.'). A valid Sudoku solution must satisfy: each row contains digits 1–9 without repetition, each column contains digits 1–9 without repetition, and each of the nine 3x3 sub-boxes contains digits 1–9 without repetition.

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: The board is filled in-place with the unique valid solution.

Input: Any valid partially-filled 9x9 board.
Output: The board is solved in-place.

We scan the board cell by cell. When we find an empty cell ('.') we try digits '1' through '9'. For each candidate we check if it is valid for the current row, column, and 3x3 box. If valid, we place it and recurse. If the recursion returns false (no solution found), we reset the cell and try the next digit.

The solve method scans left-to-right, top-to-bottom for empty cells.
If no empty cell is found, the board is fully solved — return true.
The isValid helper checks the row, column, and 3x3 box for the candidate digit.
Backtrack by resetting the cell to '.' when no digit leads to a solution.

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] != '.') continue; 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 digit worked } } return true; // all cells filled } private boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; i++) { if (board[row][i] == c) return false; if (board[i][col] == c) return false; // 3x3 box check int boxRow = 3 * (row / 3) + i / 3; int boxCol = 3 * (col / 3) + i % 3; if (board[boxRow][boxCol] == c) return false; } return true; } }

Complexity Analysis:

Time complexity: O(9^m) where m is the number of empty cells — at most 9 choices per cell.
Space complexity: O(m) for the recursion stack.