150. Solve a Sudoku Puzzle

Given a 9x9 Sudoku grid with some cells filled in and the rest marked 0, solve it (fill every cell 1-9 so each row, column, and 3x3 box contains every digit exactly once) and print the completed grid, one row per line, space-separated. Every puzzle given has exactly one solution.

Input: Nine lines, each containing 9 space-separated integers (0-9), representing the Sudoku grid with 0 marking empty cells. Output: Print the completed grid, one row per line, 9 space-separated integers per row.

The grid is always 9x9 and always has exactly one valid solution.

The problem's guarantee of EXACTLY ONE valid solution means the backtracking search can stop immediately the moment a full valid grid is found, without needing to continue searching for (nonexistent) alternative solutions.

Fill in the empty cells of a 9x9 Sudoku grid so every row, column, and 3x3 box contains every digit 1-9 exactly once. Brute force: Try every possible combination of digit assignments across all empty cells directly, checking the whole grid's validity only at the very end - this is astronomically slow, since invalid partial assignments aren't caught until the entire grid is filled. Optimised: Checking the row/column/box constraint IMMEDIATELY before recursing into each digit choice (rather than waiting until the whole grid is filled) prunes invalid branches as early as possible - most wrong digit choices are caught and abandoned within just one or two cells, not after filling dozens of cells uselessly.

Maintain a bitmask of used digits for every row, column, and 3x3 box so that checking or updating whether a digit is legal in a cell is a constant-time bitwise operation instead of scanning the row/column/box each time. Additionally, at each step choose the next empty cell that currently has the fewest legal candidate digits (the Minimum Remaining Values heuristic) rather than a fixed order, so the search fails fast on the most constrained cells first. Both refinements keep the same theoretical worst case as plain backtracking but shrink the actual search tree explored enormously, which is why this combination is the standard efficient approach for solving 9x9 Sudoku. Time: O(9^m) worst case, far fewer nodes explored Space: O(1) extra (fixed-size bitmasks) plus O(m) recursion depth

Fill empty cells one at a time in row-major order, and for each candidate digit immediately check the current row, column, and 3x3 box for conflicts before recursing into the next empty cell; if no digit works, backtrack to the previous cell and try its next candidate. This prunes invalid branches as soon as a conflict appears instead of waiting until the grid is fully filled, drastically reducing the number of grids actually explored compared to generate-and-test, even though the theoretical worst case is still exponential. Time: O(9^m) worst case, far fewer in practice Space: O(m)

Try every possible digit 1-9 in each empty cell in a fixed order, generating every combination of fillings for all empty cells, and only check at the very end whether the fully-filled grid satisfies every row, column, and box constraint. This is correct in principle because the guaranteed unique solution will eventually appear among the generated grids, but the number of combinations is astronomically large since invalid choices aren't discarded until the whole grid is complete. Time: O(9^m), m = number of empty cells, no pruning Space: O(m)

1. Find an empty cell (any systematic order, like left-to-right top-to-bottom). 2. Try placing each digit 1-9 in it, but only recurse into a choice if it doesn't immediately violate the row, column, or 3x3 box constraint. 3. Backtrack (erase the digit and try the next one) whenever a choice leads to a dead end deeper in the recursion; the puzzle is solved once every cell is successfully filled.

Time: Exponential in the worst case (bounded by 9^(number of empty cells)), though the early-pruning constraint checks make it run fast in practice for real Sudoku puzzles, which are specifically designed to have a unique, findable solution. Space: O(1) extra space beyond the grid itself (aside from the recursion stack), if constraint checks are done by scanning the grid directly; O(81) with precomputed row/column/box tracking sets for faster checks.

Test a grid with very few filled cells (heavier backtracking search) versus one that's nearly complete, since the puzzle always has exactly one solution.

Be ready to mention precomputed row/column/box 'used digits' tracking sets (updated incrementally as digits are placed/removed) as an optimization over re-scanning the grid from scratch for every single constraint check - a meaningful speedup for a problem where constraint-checking happens extremely often.