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 task

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).

Challenge 2

Before solving, check a puzzle for obvious mistakes. Write bool valid_partial(const std::vector<std::string>& g) for a 9 x 9 Sudoku with . for empty cells: true when no row, column or 3 x 3 box contains the same digit twice.

Challenge 3

A proper Sudoku has exactly one solution. Write int count_solutions(std::vector<std::string> g, int limit), which counts the solutions but stops as soon as it has found limit of them (an empty grid has billions). Backtrack like the solver, but instead of returning at the first solution, add it to the count and keep searching.

Previous: Paths through a grid