Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Sudoku Solver in Java: Try a Digit, Recurse, Restore on Failure

Solve Sudoku in place with first-empty-cell backtracking, explain row/column/box checks, and distinguish a safe trial from a complete solution.

HardRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Fill the dots in a 9×9 Sudoku board so each row, column and 3×3 box contains digits 1 through 9 exactly once. Do not change existing clues. The method updates the supplied board in place rather than returning a new board.

LeetCode Sudoku Solver guarantees one solution and supplies digits or .. The algorithm below assumes valid initial clues. It is not a general invalid-board validator; Valid Sudoku is a separate question.

The examples above use nine row strings so the whole input and output remain readable. Each string represents one row of the character matrix.

Constraints & requirements

CONTRACT
LeetCode: exactly 9×9, digits or ., and one guaranteed solution. The teaching code assumes valid clues; it is not a general invalid-board validator. The judge method returns void and updates the board.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79
    Output
    534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179

    Nine row strings describe the board. Fill every dot while preserving the original digits.

  2. Example 2 Case 2

    Input
    534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
    Output
    Same completed board

    No empty cell remains, so no mutation is needed.

  3. Example 3 Case 3

    Input
    53.678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
    Output
    Replace the first-row dot with 4; other cells unchanged

    Row, column and box constraints agree on the single missing digit.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Choose the first empty cell and try each digit 1–9.

02Hint 2

A locally legal digit must avoid conflicts in its row, column and 3×3 box.

03Hint 3

If a descendant fails, restore .; if it succeeds, keep the placements and return immediately.

How to think before coding

Find one empty cell, then try each digit that conflicts with no row, column or box entry. A successful child means KEEP the placement and stop. A failed child means restore ‘.’ before another candidate. Finding no empty cell is success under the stated valid-clue assumption. The wrapper updates the same board; it does not return a second solved board.

Brute force and the improvement

If E cells are empty, assign each one a digit 1..9 without checking conflicts until the board is complete. That explores up to 9^E assignments, with a full 81-cell validation per candidate on the fixed 9×9 board and O(E) search frames. Almost all assignments violate a clue much earlier. Check row, column and box before recursing instead. This remains a backtracking search, not a polynomial guarantee; choosing the most-constrained empty cell is an additional heuristic beyond the clear first-empty-cell implementation below.

Choose the first empty cell and ask which digit is currently allowed. A digit must not already occur in its row, column or box.

Placing a legal digit does not prove that all later cells can be filled. If a later cell has no possible completion, false returns to the caller that made the earlier choice. Restore its dot and try the next digit.

This is a search for one complete board. On success, keep the placements. Undoing the successful branch would erase the answer that the caller expects to see.

Algorithm

  1. Scan for the first dot.
  2. Try digits 1 through 9, rejecting local conflicts.
  3. Write a safe digit and recurse on the board.
  4. If the child succeeds, return true immediately.
  5. Otherwise restore the dot and try another digit.
  6. If none completes this cell, return false to the waiting caller.
  7. If the scan finds no dot, return true.

How does the box formula work?

3*(row/3) and 3*(col/3) identify the upper-left corner of the containing 3×3 box. For i=0..8, i/3 selects its local row and i%3 its local column.

For cell (4,7), the box starts at (3,6). The offsets visit (3,6),(3,7),(3,8),(4,6),…,(5,8). One nine-iteration loop can check the row, column and all box cells without confusing their coordinates.

Java solution

A void public wrapper updates the board; the boolean helper reports success internally. The no-solution exception is defensive behavior outside the guaranteed-solution contract.

Java
import java.util.*;

class Solution {
    public static void solveSudoku(char[][] board) {
        // Contract: a valid 9x9 puzzle with one solution; modify the provided board.
        if (!fillSudoku(board)) throw new IllegalArgumentException("No solution for the supplied puzzle");
    }
    private static boolean fillSudoku(char[][] board) {
        for (int row = 0; row < 9; row++) for (int col = 0; col < 9; col++) {
            if (board[row][col] != '.') continue; // Preserve every given clue.
            for (char digit = '1'; digit <= '9'; digit++) {
                if (!sudokuSafe(board, row, col, digit)) continue; // Check row, column AND box.
                board[row][col] = digit; // Choose a locally legal value.
                if (fillSudoku(board)) return true; // Keep all successful placements; do not undo them.
                board[row][col] = '.'; // Dead end later: restore this cell before another digit.
            }
            return false; // THIS first empty cell had no successful value; tell the waiting caller.
        }
        return true; // No empty cell remains; validity follows from valid clues and safe placements.
    }
    private static boolean sudokuSafe(char[][] board, int row, int col, char digit) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == digit || board[i][col] == digit) return false; // Row and column.
            int boxRow = 3 * (row / 3) + i / 3, boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == digit) return false; // Traverse all nine cells of the correct box.
        }
        return true; // A local permission to try, not proof the whole puzzle is solvable.
    }

    public static void main(String[] args) {
        char[][] board = {
            "53..7....".toCharArray(), "6..195...".toCharArray(), ".98....6.".toCharArray(),
            "8...6...3".toCharArray(), "4..8.3..1".toCharArray(), "7...2...6".toCharArray(),
            ".6....28.".toCharArray(), "...419..5".toCharArray(), "....8..79".toCharArray()
        };
        solveSudoku(board); // Modifies this board, returns no separate result.
        for (char[] row : board) System.out.println(new String(row)); // Solved rows, starting 534678912.
    }
}

The driver prints the solved nine rows shown in Example 1. Existing clues remain unchanged. A fully filled valid board returns without making any new placements.

Recursion tree and dry run

Numbered illustrated dry run for Sudoku Solver; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: the article’s 9×9 puzzle, whose first row is "53..7...."

What to track: A call scans for the first dot in row-major order. row/col identify that dot; digit is a tentative choice. Long descendant searches below are summarized explicitly, not presented as consecutive instructions.

  1. Find the first empty cell

    Java operationif (board[row][col] != '.') continue;
    Staterow = 0; col = 2; board[0][2] = '.'

    The scan skips the given 5 and 3. A clue is never overwritten.

  2. Try the first locally safe digit

    Java operationboard[row][col] = digit;
    Statedigit = '1'; first row becomes "531.7...."

    sudokuSafe checks the row, column and 3×3 box first. Locally safe means permission to try, not proof the puzzle is solved.

  3. Search below this guess

    Java operationif (fillSudoku(board)) return true;
    Statethe child tries later dots; eventually this entire digit-1 subtree returns false

    The known unique solution has 4 at (0,2), so no completion can retain this 1. This row summarizes many recursive calls.

  4. Restore the failed guess

    Java operationboard[row][col] = '.';
    Stateresumed caller restores board[0][2]; first row is "53..7...." again

    Failed descendants have already restored their own dots. This caller restores only the cell it chose.

  5. Try 2, then reject 3

    Java operationif (!sudokuSafe(board, row, col, digit)) continue;
    Statedigit 2 is locally safe but its descendant search also fails and is undone; digit 3 conflicts with the existing row clue

    No recursive child is created for 3. The next permitted digit at this cell is 4.

  6. Keep the successful continuation

    Java operationif (fillSudoku(board)) return true;
    Statechoose 4 at (0,2); eventually no dots remain; the terminal call returns true

    Every waiting caller returns immediately on true, so the chosen digits remain on the board. Undoing on success would erase the solution.

Final result: the complete solved board, with first row "534678912"; all original clues preserved.

The sample’s first dot is (0,2). Its row contains 5,3,7; its column already has 8; its box contains 5,3,6,9,8. The locally allowed candidates are 1,2,4.

Worked example · read from top to bottom
first empty cell (0,2)
├─ try 1 → locally safe → explore descendants
│  └─ eventually a dead end → false → restore .
├─ try 2 → locally safe → explore descendants
│  └─ eventually a dead end → false → restore .
└─ try 4 → explore descendants → complete solution → true
   keep 4 and every later successful placement

This is a summarized tree, not an immediate failure at the very next cell. The supplied puzzle has one solution, whose (0,2) value is 4; the earlier locally legal branches cannot complete it.

Return from a child What the caller does Why
false Restore its chosen cell to . That digit did not permit a complete solution
true Return true without restoration The board now holds the answer
No empty cell found Return true All placements are complete and constraints were preserved

Each caller remembers the cell whose choice it owns. The next recursive scan does not transfer ownership of that cell to another frame.

Why it works

Given consistent clues, every tentative placement passes all three constraint checks, preserving local Sudoku validity. If there are no empty cells, each nine-cell row, column and box contains nine different digits from 1..9 and therefore contains the whole required set.

At an empty cell, every safe digit is tried. Any full solution extending the current board uses one of those digits, so no solution is missed. Restoring failed placements makes siblings independent. Returning on success preserves the solved board in the original object.

Complexity and alternative approaches

Let E be the initial number of empty cells. A loose worst-case bound is O(9^E) search: each level fills one empty cell and has at most nine digit choices. The 81-cell scan and nine-step safety checks are constants for this fixed 9×9 task, though they affect practical runtime.

Recursive auxiliary space is O(E). The board is modified in place and no alternative boards are copied. For a fixed 9×9 grid, E≤81; parameterizing by E makes the search growth clearer than saying only “constant.”

Row/column/box masks can speed up safety checks. Choosing the empty cell with the fewest legal candidates often prunes more strongly than row-major order. Those optimizations need careful updates and restoration. Merely validating the initial board neither solves it nor proves that it has a completion.

Common mistakes

  • Forgetting the box test or using the wrong box offsets.
  • Treating the first locally allowed digit as final.
  • Undoing after a successful return and erasing the answer.
  • Returning false only after scanning unrelated empty cells instead of failing the current choice.
  • Claiming that no dots proves an arbitrary invalid starting board is valid; the clue-validity assumption matters.

Practice next

Next lessonN-Queens

Back to Recursion and backtracking →