Project Euler Problem 96

Solution

Answer: 24702

The key to this problem is not deep number theory, but designing a reliable and efficient exact-search algorithm for solving Sudoku puzzles.

A Sudoku grid is a constraint satisfaction problem:

• Each row must contain digits $1$–$9$ exactly once.
• Each column must contain digits $1$–$9$ exactly once.
• Each $3\times3$ box must contain digits $1$–$9$ exactly once.

The Project Euler task provides 50 puzzles, each with a unique solution. For each solved puzzle, we extract the 3-digit number formed by the first three digits of the top row and sum them.

---

Mathematical Analysis

Suppose a cell is empty.

Let:

• $R$ = digits already used in its row,
• $C$ = digits already used in its column,
• $B$ = digits already used in its $3\times3$ box.

Then the allowed candidates are

$${1,\dots,9}\setminus (R\cup C\cup B).$$

A puzzle is solved when every cell has exactly one value.

---

Backtracking Search

Pure logical deduction is not sufficient in general, so we use recursive search.

Strategy

1. Find the empty cell with the fewest candidates.
2. Try each candidate.
3. Recurse.
4. If a contradiction occurs, backtrack.

This “minimum remaining values” heuristic is extremely important because it dramatically prunes the search tree.

---

Efficient Representation

We can represent constraints using sets.

For each row, column, and box, maintain the digits already used.

For a cell $(r,c)$:

$$\text{box}(r,c)=3\left\lfloor \frac r3 \right\rfloor+\left\lfloor \frac c3 \right\rfloor.$$

Candidate digits are computed quickly from set differences.

---

Python Implementation

from urllib.request import urlopen

# Download the Sudoku file
url = "https://projecteuler.net/project/resources/p096_sudoku.txt"
data = urlopen(url).read().decode().strip().splitlines()

# Parse puzzles
puzzles = []
for i in range(0, len(data), 10):
    grid = [list(map(int, data[i + j + 1])) for j in range(9)]
    puzzles.append(grid)

DIGITS = set(range(1, 10))

def solve(grid):
    """
    Solve a Sudoku puzzle using recursive backtracking
    with minimum-candidate heuristic.
    """

    # Track used digits
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize constraint sets
    for r in range(9):
        for c in range(9):
            v = grid[r][c]
            if v:
                rows[r].add(v)
                cols[c].add(v)
                boxes[(r // 3) * 3 + (c // 3)].add(v)

    def backtrack():
        best = None
        best_candidates = None

        # Find empty cell with fewest candidates
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    b = (r // 3) * 3 + (c // 3)

                    candidates = (
                        DIGITS
                        - rows[r]
                        - cols[c]
                        - boxes[b]
                    )

                    if len(candidates) == 0:
                        return False

                    if best is None or len(candidates) < len(best_candidates):
                        best = (r, c, b)
                        best_candidates = candidates

        # No empty cells => solved
        if best is None:
            return True

        r, c, b = best

        # Try each candidate
        for v in best_candidates:
            grid[r][c] = v
            rows[r].add(v)
            cols[c].add(v)
            boxes[b].add(v)

            if backtrack():
                return True

            # Undo move
            grid[r][c] = 0
            rows[r].remove(v)
            cols[c].remove(v)
            boxes[b].remove(v)

        return False

    backtrack()
    return grid

total = 0

for puzzle in puzzles:
    solved = solve(puzzle)

    # Extract top-left 3-digit number
    value = (
        solved[0][0] * 100
        + solved[0][1] * 10
        + solved[0][2]
    )

    total += value

print(total)

---

Code Walkthrough

Parsing the file

Each puzzle in the text file has:

• one header line like Grid 01
• followed by 9 rows of digits.

We process blocks of 10 lines at a time.

for i in range(0, len(data), 10):

and convert rows into integer lists.

---

Constraint Tracking

We maintain:

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

These store which digits are already used.

The box index is:

(r // 3) * 3 + (c // 3)

giving values $0$ through $8$.

---

Candidate Computation

For an empty cell:

candidates = DIGITS - rows[r] - cols[c] - boxes[b]

This directly implements Sudoku legality constraints.

---

Minimum-Candidate Heuristic

We search for the hardest cell first:

if best is None or len(candidates) < len(best_candidates):

This reduces branching dramatically.

---

Recursive Backtracking

For each candidate:

grid[r][c] = v

we update constraints, recurse, and undo if necessary.

This guarantees an exact solution because every legal possibility is explored systematically.

---

Verification on the Example Puzzle

The first example puzzle in the statement solves to a grid whose top-left corner is:

$$483$$

which matches the problem statement exactly.

So the extraction logic is correct.

---

Final Verification

The result should:

• be positive,
• consist of the sum of 50 three-digit numbers,
• therefore lie roughly between $50\times100=5000$ and $50\times999=49950$.

The computed result:

$$24702$$

fits perfectly in this range.

Therefore the solution is consistent.

---

Answer: 24702