Skip to content
Tutorials Center
My learning

Topics

Lesson 188 of 201 ยท Projects

Project: Sudoku Solver

Build a Java Sudoku validator and solver with backtracking, then speed it up with bitmasks and the fewest-candidates rule, count solutions and generate puzzles with one answer.

Sudoku is a gift to programmers. The rules fit in one sentence (every row, column and 3x3 box contains each digit from 1 to 9 exactly once), a human can solve one in minutes, and the search a computer needs to do it is a textbook example of backtracking: try something, see whether it leads to a contradiction, and undo it if it does.

You'll build the project in three stages. First a board that can be parsed, printed and validated, because a solver that trusts its input will happily "solve" an impossible grid. Then the simplest possible backtracking solver, with a trace so you can watch it try and undo digits. Finally a faster solver using bitmasks and the fewest-candidates-first rule, which can also count solutions (to check that a puzzle has exactly one answer) and generate new puzzles.

You'll practice two-dimensional arrays, recursion, the backtracking pattern from algorithm patterns, bitwise operators and sets and lists.

Representing the board

The board is 81 cells. Two conventions keep everything short:

  • Text form: an 81-character string, row by row, with . (or 0) for an empty cell. It's easy to paste into a program, a file or the Input box below.
  • Digits: 0 means empty and 1 to 9 are digits.

A cell at row r and column c (both starting at 0) belongs to box number (r / 3) * 3 + c / 3, counting boxes left to right and then top to bottom. A digit can go in a cell if it isn't already in that cell's row, column or box.

Stage 1: parsing, printing and validating

Java Stage 1: the board, candidates and validation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The output shows what a validator can say:

  • The puzzle has 30 clues and no problems.
  • Only 5, 6, 7 and 9 fit at row 1, column 1. Everything else is already in that cell's row, column or box. Listing such candidates for an empty cell is the core operation of every Sudoku program.
  • Typing a 4 in the corner creates conflicts: findProblems checks all 27 units (9 rows, 9 columns, 9 boxes) and reports each one that contains a repeated digit. The expression grid[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] walks the cells of box i: i / 3 is the box row, i % 3 the box column, and j / 3, j % 3 the position inside the box.

Validating first matters because a solver will always terminate with some answer, even if that answer is "no solution", and the reason matters to the user: "your clues contradict each other" is a different message from "this puzzle is unsolvable".

The idea of backtracking

Imagine solving by hand with no cleverness. Find an empty cell, write the smallest digit that doesn't break a rule, and move on. Sooner or later you reach a cell where no digit fits. That means an earlier guess was wrong. You walk back to the most recent guess, erase it, try its next digit, and carry on. That walk-back is backtracking, and the code mirrors the story exactly:

TEXT
solve():
    find the first empty cell
    if there is none: the grid is full, success
    for each digit 1..9 that fits there:
        place it
        if solve() succeeds: success
        remove it            <- the "undo" that makes it backtracking
    nothing worked: failure (the caller will try its next digit)

The recursion stack is the "memory" of earlier guesses, so there's no need to store them yourself. Three details make or break an implementation:

  1. Every placement must be undone when the recursive call fails. Forgetting the grid[r][c] = 0 line leaves wrong digits on the board.
  2. A dead end returns false right after the digit loop. Without it the loop would continue to the next empty cell and try digits there, which wastes effort and hides the contradiction.
  3. The first return value true unwinds everything. Once solved, every caller returns true immediately and leaves the digits in place.

Stage 2: the simple backtracking solver

This version has a counter for placements tried and prints the first 14 events, so you can see the trial and error happening. It then solves the same puzzle and a famously difficult one.

Java Stage 2: a naive backtracking solver with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

In the trace, the early events are all try lines: the solver is filling the first row with digits that happen to fit locally. The undo lines only start once a later cell has no candidate left, and they undo whatever was placed most recently. The isCompleteAndValid check proves that the final grid is a real solution, independent of the solver: it lifts each digit off the board and asks canPlace whether it could be put back.

The counters show the weakness. The puzzle with 30 clues takes 1,017 placements. The famously difficult one takes 49,558, because the solver always works on the first empty cell in reading order, even when that cell has many candidates. It guesses where it could be making forced moves. For puzzles built to defeat this strategy, the count explodes into the millions.

Stage 3: faster, with bitmasks and the fewest-candidates rule

Two changes make a big difference.

Bitmasks instead of loops. Keep three arrays of nine integers, for rows, columns and boxes. In each integer, bit d is 1 if digit d is already used there. Then:

  • The candidates of a cell are the digits that appear in none of its three masks: ~(row | column | box) & 0x3FE. The mask 0x3FE keeps bits 1 to 9 and ignores bit 0.
  • Placing a digit sets one bit in three masks (|=), and removing it clears them (&= ~bit). No loops over nine cells.
  • How many candidates a cell has is Integer.bitCount(mask).

Choose the most constrained cell first. Instead of the first empty cell, pick the one with the fewest candidates. A cell with one candidate is a forced move: no guessing at all. A cell with zero candidates reveals a dead end immediately, long before the naive solver would stumble into it. This heuristic is called minimum remaining values (MRV).

Once the solver is fast, counting solutions is a small variation: instead of stopping at the first full grid, keep searching and add up the grids you find, with a limit. We stop at 2, because "none, one or more than one" is all we need. That makes two more features easy:

  • check reports whether a puzzle has no solution, exactly one or more than one. A proper Sudoku has exactly one.
  • generate builds a random complete grid by shuffling a valid pattern (relabeling the digits and permuting rows and columns within their bands and stacks, which keeps every unit valid), then removes cells in random order, keeping a removal only if the puzzle still has a unique solution.

The Solver constructor validates the givens as it places them, so a contradictory puzzle fails early with a message that names the cell.

Java Stage 3: the complete solver, checker and generator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Go through the output:

  • generate 7 30 and generate 11 24 print puzzles with 30 and 24 clues, and each has exactly one solution because the generator only keeps cells it can remove without losing uniqueness. The same seed always gives the same puzzle. Fewer clues usually means a harder puzzle; the smallest known proper puzzles have 17.
  • compare hard runs the same famous puzzle with both strategies: 49,558 placements for first-empty-cell-first against 13,810 for fewest-candidates-first, with identical answers. The smart choice isn't magic: with no deduction at all, it only reorders the search, but that already cuts the work by about three quarters here. On puzzles built to defeat the naive order, the gap is far larger.
  • check classifies puzzles. The first one has no contradiction among its clues, but its top-right cell can't take any digit (1 to 8 are in its row and the 9 below it blocks the last one), so it reports no solution. The second one is refused by the constructor: two 1s in one row, with the position of the second.
  • solve on the 30-clue puzzle needs only 51 placements, compared with 1,017 for the naive version in Stage 2. Most moves are forced.
  • Malformed input (wrong length, unknown command) is reported by SudokuException, one place in main.

Design notes

  • State is mutated and restored. put and clear are exact inverses, so the search can undo any move. countSolutions leaves the solver exactly as it found it, which is why generate can reuse the same puzzle array between checks.
  • chooseCell can stop early. If a cell has zero or one candidate, nothing can beat it, so the scan ends.
  • Counting needs a limit. Without limit, a nearly empty grid has about 6.67 sextillion solutions and the program would never finish.
  • Why 0x3FE? In binary that is 1111111110: bits 1 to 9 set, bit 0 clear. ~used flips every bit, and the & keeps only the nine digit bits.
  • Constants and magic numbers. (cell / 27) * 3 + (cell % 9) / 3 converts a cell index (0 to 80) to its box. Name tiny helpers like boxOf so the formula lives in one place.

Ideas to extend it

  • Add constraint propagation: after placing a digit, if some unit has a digit with only one possible cell ("hidden single"), place it without searching.
  • Add a human-style hint command that explains one logical step ("only cell in row 3 where a 7 fits") instead of giving away the answer.
  • Solve Sudoku variants: diagonal Sudoku (two extra units), or a 16x16 board with hexadecimal digits.
  • Read puzzles from a file with Files.readAllLines, solve each one and print timing statistics.
  • Draw the board in a Swing grid of text fields and call the solver from a button.
  • Measure how the number of placements grows for puzzles with 40, 30 and 25 clues using generate.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What makes a search "backtracking" rather than plain trial and error?

    Backtracking explores one choice at a time and, when a branch leads to a dead end, removes that choice and continues with the next. The undo step (and the recursion stack remembering earlier choices) is the defining feature.
  2. 2. In the bitmask solver, what does ~(row | column | box) & 0x3FE compute?

    OR-ing the three masks gives all digits used in the row, column or box. The complement flips that to the unused digits, and 0x3FE keeps only bits 1 to 9.
  3. 3. Why does picking the cell with the fewest candidates usually make the search faster?

    A cell with one candidate has only one possible move, and a cell with none shows immediately that an earlier choice was wrong. Both shrink the search tree a lot.
  4. 4. Why does countSolutions take a limit, and why do check and generate pass 2?

    Sparse grids can have astronomically many solutions. Stopping at 2 is enough to tell a proper puzzle (exactly one) from an ambiguous one.

Summary

  • Represent the board as 81 cells in an int[] (or int[9][9]), and validate every unit (row, column and box) before solving.
  • Backtracking is recursion with an explicit undo: choose, explore, un-choose. A dead end returns false right after the loop.
  • Bitmasks (|=, &= ~bit, Integer.bitCount) make "which digits are still possible" a constant-time operation.
  • Choosing the most constrained cell first turns many guesses into forced moves and cuts the search dramatically.
  • Counting solutions with a limit lets you check puzzle quality and generate puzzles whose answer is unique.
  • Keep the solver's state changes symmetric (put/clear) so searches can leave it exactly as they found it.

Next: Project: Supermarket Billing System, where you will model discounts with a sealed interface and print an aligned receipt using exact BigDecimal money.