Crack the Backend

Problem Statement

Given a 9×9 Sudoku board (partially filled; cells are '1'-'9' or '.' for empty), solve the puzzle by filling empty cells so that each row, each column, and each of the nine 3×3 sub-boxes contains the digits 1–9 exactly once. Modify the board in-place; assume that the input has exactly one solution.

We fill empty cells one by one. For each empty cell, try digits 1–9; for each digit check that it does not already appear in the same row, column, or 3×3 box. If valid, place it and recurse; if the recursion returns true we are done; else remove the digit (backtrack) and try the next.

Key Observations

Backtracking: Find the next empty cell (or scan in order). If there is no empty cell, the board is full — return true. For digit d from 1 to 9: if placing d in this cell is valid (no same d in its row, column, or 3×3 box), set board[r][c] = d, call solve(); if it returns true, return true. Otherwise set board[r][c] = '.' and try the next digit. If no digit works, return false.
To check validity in O(1), we can precompute or use sets for each row, column, and box. Box index for (r,c) is (r/3)*3 + c/3.

Approach

High-level: Find next empty cell. If none, return true. For d = '1'..'9': if valid at (r,c), board[r][c]=d, if solve() return true, board[r][c]='.'. Return false. valid: no same in row, col, or 3×3 box.

Steps: Helper valid(r, c, d) checks row r, col c, and box (r/3, c/3). solve(): find (r,c) with board[r][c]=='.'; if not found return true. For each d in '1'..'9': if valid(r,c,d), set board[r][c]=d, if solve() return true, set board[r][c]='.'. Return false.

Implementation

Java

public void solveSudoku(char[][] board) {
    solve(board);
}

boolean solve(char[][] b) {

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (b[i][j] != '.') {
                continue;
            }

            for (char c = '1'; c <= '9'; c++) {
                if (valid(b, i, j, c)) {
                    b[i][j] = c;

                    if (solve(b)) {
                        return true;
                    }

                    b[i][j] = '.';
                }
            }

            return false;
        }
    }

    return true;
}

boolean valid(char[][] b, int r, int c, char ch) {

    for (int i = 0; i < 9; i++) {
        if (b[r][i] == ch || b[i][c] == ch) {
            return false;
        }

        if (b[3*(r/3)+i/3][3*(c/3)+i%3] == ch) {
            return false;
        }
    }

    return true;
}

Test Cases

Standard

Input

9x9 board with some filled

Expected

Solved board

Explanation

All rows/cols/boxes valid.

Complexity Analysis

Time: O(9^m) m = empty cells.
Space: O(1) in-place.

Follow-ups

Validate Sudoku: check if current board is valid.