Introduction

A Sudoku generator is harder to build than a Sudoku solver because you are optimizing for two outcomes at once: a valid puzzle and exactly one final solution. The standard approach is to generate a complete solved grid, remove clues one at a time, and test uniqueness after each removal. This article shows a practical design that produces varied boards while keeping generation time predictable.

Core Sections

Use Two Solvers with Different Jobs

A maintainable generator usually has two related solvers:

1. A randomized solver that fills an empty board to create a complete valid solution.
2. A counting solver that returns how many solutions a partially filled puzzle has, stopping as soon as it finds more than one.

Keeping these responsibilities separate makes the code easier to reason about and optimize.

1from __future__ import annotations
2from typing import List, Optional, Tuple
3import random
4
5Board = List[List[int]]
6
7
8def find_empty(board: Board) -> Optional[Tuple[int, int]]:
9    for r in range(9):
10        for c in range(9):
11            if board[r][c] == 0:
12                return r, c
13    return None
14
15
16def is_valid(board: Board, row: int, col: int, num: int) -> bool:
17    if any(board[row][c] == num for c in range(9)):
18        return False
19    if any(board[r][col] == num for r in range(9)):
20        return False
21
22    box_row = (row // 3) * 3
23    box_col = (col // 3) * 3
24    for r in range(box_row, box_row + 3):
25        for c in range(box_col, box_col + 3):
26            if board[r][c] == num:
27                return False
28    return True

Step 1: Build a Fully Solved Grid

Generation starts with an empty nine by nine board. The randomized solver tries candidates one through nine in shuffled order, which gives different completed grids across runs.

1def solve_random(board: Board, rng: random.Random) -> bool:
2    pos = find_empty(board)
3    if pos is None:
4        return True
5
6    r, c = pos
7    nums = list(range(1, 10))
8    rng.shuffle(nums)
9
10    for n in nums:
11        if is_valid(board, r, c, n):
12            board[r][c] = n
13            if solve_random(board, rng):
14                return True
15            board[r][c] = 0
16
17    return False
18
19
20def make_solved_board(seed: int | None = None) -> Board:
21    rng = random.Random(seed)
22    board = [[0 for _ in range(9)] for _ in range(9)]
23    if not solve_random(board, rng):
24        raise RuntimeError("Failed to generate solved board")
25    return board

Passing an explicit seed is useful for tests because it makes outputs reproducible.

Step 2: Enforce Uniqueness While Removing Clues

After you have one solved grid, remove values cell by cell. For each tentative removal, count solutions. Keep the removal only when the count is exactly one.

1def count_solutions(board: Board, limit: int = 2) -> int:
2    pos = find_empty(board)
3    if pos is None:
4        return 1
5
6    r, c = pos
7    total = 0
8    for n in range(1, 10):
9        if is_valid(board, r, c, n):
10            board[r][c] = n
11            total += count_solutions(board, limit)
12            board[r][c] = 0
13            if total >= limit:
14                break
15    return total
16
17
18def generate_unique_puzzle(removals: int = 45, seed: int | None = None) -> Board:
19    rng = random.Random(seed)
20    board = make_solved_board(seed)
21
22    cells = [(r, c) for r in range(9) for c in range(9)]
23    rng.shuffle(cells)
24
25    removed = 0
26    for r, c in cells:
27        if removed >= removals:
28            break
29
30        saved = board[r][c]
31        board[r][c] = 0
32
33        trial = [row[:] for row in board]
34        if count_solutions(trial, limit=2) == 1:
35            removed += 1
36        else:
37            board[r][c] = saved
38
39    return board

The limit=2 cutoff is critical for speed. You do not need the exact number once you know there is more than one solution.

Difficulty Is Not the Same as Uniqueness

A puzzle with one solution can still be trivial or very hard. Clue count alone is an imperfect proxy. If your product needs difficulty labels, add a rating pass that emulates human techniques such as naked singles, hidden singles, and pairs before allowing trial-and-error.

A practical pipeline is:

1. Generate and uniqueness-check puzzle.
2. Run a deterministic difficulty rater.
3. Keep only puzzles that fit desired bands such as easy, medium, hard.

This separation keeps generator logic clean and avoids guessing based on clue count.

Operational Considerations

Uniqueness checking is the expensive part, so most teams pre-generate puzzles in the background and store them. That gives stable response times for players and avoids heavy CPU spikes at request time.

Good production checks include:

• verify every puzzle has one solution before publishing
• store the solved board for answer validation
• track generation time metrics for tuning
• run periodic integrity checks on stored puzzles

Common Pitfalls

• Removing many clues in one pass and checking uniqueness only at the end, which often creates multiple solutions.
• Reusing mutable board references between recursion branches, causing subtle state corruption.
• Assuming fewer clues always means harder gameplay, which leads to inaccurate difficulty labels.
• Counting all possible solutions instead of stopping at two, which wastes significant CPU time.
• Skipping seeded test cases, making generator regressions hard to reproduce.

Summary

• Build a complete solved board first with randomized backtracking.
• Remove clues incrementally and keep each removal only if solution count remains one.
• Use a dedicated counting solver with an early stop at two solutions.
• Treat uniqueness and difficulty as separate concerns in your pipeline.
• Pre-generate and validate puzzles for predictable production behavior.