L15. Sudoku Solver | Backtracking

1. Why Do We Need This? (Problem Statement & Status Quo)

Sudoku is a classic number-placement puzzle played on a $9 \times 9$ grid. When given an incomplete puzzle with some pre-filled digits and many empty cells, the objective is to fill the remaining empty positions following strict mathematical constraints.

• The Challenge: An incomplete Sudoku puzzle can have multiple valid configurations or require exploring deep decision trees to find the single correct arrangement.
• The Core Constraint: Because we must test various combinations of numbers ($1$ through $9$) across rows, columns, and sub-grids, brute-force iteration without structure results in exponential time complexity. We need an intelligent search strategy that abandons invalid paths early—Backtracking.

2. Core Mental Model & The Three Sudoku Rules

A standard Sudoku board is a $9 \times 9$ matrix composed of nine smaller $3 \times 3$ sub-boards (or boxes).

[3x3 Box 0] [3x3 Box 1] [3x3 Box 2]
[3x3 Box 3] [3x3 Box 4] [3x3 Box 5]
[3x3 Box 6] [3x3 Box 7] [3x3 Box 8]

To successfully solve or validate any state on the board, three strict rules must be satisfied at all times:

1. Row Rule: Each digit from $1$ to $9$ must appear exactly once in any given row.
2. Column Rule: Each digit from $1$ to $9$ must appear exactly once in any given column.
3. Sub-Grid Rule: Each digit from $1$ to $9$ must appear exactly once in any given $3 \times 3$ sub-board.

3. The Backtracking Strategy: Trying All Possible Ways

Since Sudoku requires filling empty cells with numbers $1$ through $9$, the problem maps directly to a recursive backtracking template:

• Scan the Board: Traverse the matrix from top-left to bottom-right to find the first empty cell (represented by a placeholder or zero/dot character).
• Branching Choices: For that empty cell, try placing digits from $1$ to $9$ one by one.
• Safety Check (isvalid): Before making a recursive call with a chosen digit, verify that placing the number does not violate the row, column, or $3 \times 3$ box rules.
• Recursive Leap: If valid, place the number and recursively call the solver function for the next state.
• Backtracking (Undo): If the recursive call returns false (meaning the choice led to a dead end down the road), undo the choice (reset the cell to empty) and try the next digit.

4. Step-by-Step Flow Walkthrough (Mental Dry Run)

Let us trace how the algorithm evaluates an empty cell:

1. Find First Empty Cell: The algorithm scans row by row, column by column, and stops at the very first empty coordinate.
2. Test Digits ($1$ to $9$):
   • Try placing 1. Check if 1 exists in the current row, column, or $3 \times 3$ box.
   • If valid, update the board with 1 and trigger solve(board).
3. Deeper Recursion & Dead Ends:
   • The recursive call moves to subsequent empty cells.
   • If a later cell hits a state where no numbers ($1-9$) can be legally placed, that branch returns false.
   • Upon receiving false, the algorithm backtracks, removes 1, and tries the next candidate (e.g., 4).
4. Successful Completion:
   • If a choice leads to filling every empty cell without rule violations, the base case detects no empty cells remaining and returns true all the way up the call stack.

5. Complete C++ Code Implementation

Below is the complete, production-grade C++ solution implementing Sudoku solving via recursion and backtracking:

#include <vector>
#include <iostream>

class Solution {
public:
    void solveSudoku(std::vector<std::vector<char>>& board) {
        solve(board);
    }

private:
    bool solve(std::vector<std::vector<char>>& board) {
        // Traverse the entire 9x9 board
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                
                // Found an empty cell
                if (board[i][j] == '.') {
                    
                    // Try digits '1' through '9'
                    for (char c = '1'; c <= '9'; c++) {
                        
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c; // Make choice
                            
                            // Recursively attempt to solve for the rest of the board
                            if (solve(board)) {
                                return true; // Found valid solution
                            }
                            
                            // Backtrack: Undo choice if it didn't lead to a solution
                            board[i][j] = '.';
                        }
                    }
                    
                    // If no digit from '1' to '9' works, return false
                    return false;
                }
            }
        }
        // If no empty cells remain, the puzzle is solved
        return true;
    }

    bool isValid(std::vector<std::vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check Row
            if (board[row][i] == c) return false;
            
            // Check Column
            if (board[i][col] == c) return false;
            
            // Check 3x3 Sub-grid
            // Formula maps 9 individual cells of the local 3x3 box
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == c) return false;
        }
        return true;
    }
};

6. Mathematical Genius: O(1) Validation in a Single Loop

Writing separate loops to check rows, columns, and $3 \times 3$ sub-matrices is inefficient and verbose. The isValid function brilliantly checks all three constraints simultaneously within a single loop running from i = 0 to 8.

Deconstructing the 3x3 Box Indexing Formula

To check the current $3 \times 3$ sub-grid containing cell (row, col), we use the following coordinate mappings as i goes from 0 to 8:

• Why divide by 3? Since each sub-board has a dimension of $3$, integer division (row / 3) identifies which of the 3 vertical or horizontal block sections the cell belongs to.
• Why multiply by 3? Multiplying back by $3$ shifts our coordinate reference to the exact starting index (top-left corner) of that specific $3 \times 3$ sub-grid.
• Why use modulo 3 (i % 3)? As i increments from $0$ to $8$, i / 3 steps through the 3 rows of the sub-grid, while i % 3 cycles through the 3 columns (0, 1, 2, 0, 1, 2, ...).

7. Summary and Key Takeaways

• Problem Nature: Sudoku solving is a combinatorial search problem solved efficiently using recursive backtracking.
• Three Rules: Every valid configuration must satisfy unique digit appearances ($1-9$) across every row, every column, and every $3 \times 3$ sub-grid.
• State Space Exploration: The algorithm scans for the first empty cell (.), branches into 9 potential choices ($1$ through $9$), and validates each via isValid().
• The Power of Backtracking: If a recursive branch encounters a dead end (returns false), the algorithm immediately backtracks by resetting the cell to empty (.) and testing the next numeric option.
• Early Exit Optimization: Because the problem asks for a valid Sudoku solution rather than all possible permutations, execution terminates and returns true the moment the first successful completion is found.
• Elegant Validation: Row, column, and $3 \times 3$ box constraints are verified concurrently inside a single compact loop using integer division and modulo arithmetic.