Step 6 of 6

A Sudoku solver

Sudoku is backtracking's showcase. A 9 × 9 grid must be filled with digits so that every row, every column and every 3 × 3 box contains 1 to 9 exactly once. Humans solve it with clever deductions. A computer can solve almost any puzzle with the plain recipe from this module:

1. Find an empty cell. If there isn't one, the grid is full: solved.
2. Try each digit 1 to 9 that doesn't already appear in that cell's row, column or box.
3. Place it, and recursively solve the rest. If that succeeds, done.
4. If it fails, erase the digit and try the next one. If no digit works, return false: an earlier guess was wrong, and the caller will try its next digit.

The givens constrain the search heavily, so a typical newspaper puzzle is solved after a few thousand placements, which takes milliseconds.

Which box?

The 3 × 3 box containing cell (r, c) starts at row r / 3 * 3 and column c / 3 * 3 (integer division rounds down). Cell (4, 7) is in the box starting at (3, 6). To check a digit against its box, loop over the 9 cells from that corner:

#include <iostream>
#include <string>
#include <vector>

bool can_place(const std::vector<std::string>& g, int r, int c, char d) {
    for (int i = 0; i < 9; i++) {
        if (g[r][i] == d) return false;                          // same row
        if (g[i][c] == d) return false;                          // same column
        if (g[r / 3 * 3 + i / 3][c / 3 * 3 + i % 3] == d) return false;   // same box
    }
    return true;
}

int main() {
    std::vector<std::string> g = {
        "53..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79",
    };
    std::cout << "digits that fit at (0, 2): ";
    for (char d = '1'; d <= '9'; d++)
        if (can_place(g, 0, 2, d)) std::cout << d << " ";
    std::cout << "\n";
}

digits that fit at (0, 2): 1 2 4

How it works

• One loop of 9 checks all three groups: g[r][i] walks the row, g[i][c] walks the column, and i / 3 and i % 3 turn i into a row and column offset inside the box (0,0), (0,1), (0,2), (1,0) and so on.
• Row 0 already has 5, 3 and 7, column 2 has 8, and the top-left box has 5, 3, 6, 9 and 8. That leaves 1, 2 and 4 for the solver to try, in that order.

Now the search itself. The grid is the only state: placing a digit is the choice, and writing '.' back is the un-choice. If the first empty cell has no digit that fits, return false straight away, which also makes an impossible puzzle fail quickly instead of searching forever.

Your turn: write solve(grid). Empty cells are '.'. Fill the grid in place and return true, or return false if the puzzle has no solution (the grid's contents don't matter then).

Previous: Paths through a grid