Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 41 ยท Projects and Practice

Project: Build a Sudoku Game with Pygame

Build Sudoku in Pygame: board model, rule checking, backtracking solver with the most-constrained-cell heuristic, puzzle generator with unique solutions, mouse and keyboard GUI.

Sudoku is the perfect project for a programmer: the rules fit on a postcard, the board is a tidy 9 by 9 grid, and the interesting parts, checking rules, solving by backtracking and generating puzzles, are classic algorithms. The GUI adds selection, number entry, mistake highlighting and a hint button.

As in the previous projects, the logic is a plain Python class that runs and is tested here. The Pygame window is read-only code for your own computer.

The rules and the data model

Fill a 9 by 9 grid with digits 1 to 9 so that every row, every column and every 3 by 3 box contains each digit exactly once. A puzzle starts with some cells filled in (the "givens"), which the player cannot change.

We store the grid as a list of 81 integers, with 0 meaning empty. Cell i is in row i // 9, column i % 9 and box (row // 3) * 3 + col // 3.

flowchart LR
  G["grid[81]"] --> R["row = i // 9"]
  G --> C["col = i % 9"]
  G --> B["box = (row // 3) * 3 + col // 3"]
  R --> P["peers: 20 cells that<br/>share row, column or box"]
  C --> P
  B --> P

Every cell has exactly 20 "peers": 8 in its row, 8 in its column and 4 more in its box.

The peers of a cell are the cells that may not hold the same digit. Precomputing them once makes every rule check a short loop:

Python
def peers_of(i):
    r, c = divmod(i, 9)
    br, bc = r // 3 * 3, c // 3 * 3
    result = set()
    for k in range(9):
        result.add(r * 9 + k)                    # row
        result.add(k * 9 + c)                    # column
        result.add((br + k // 3) * 9 + bc + k % 3)   # box
    result.discard(i)
    return result

PEERS = [peers_of(i) for i in range(81)]

def candidates(grid, i):
    """Digits that can still go in cell i."""
    used = {grid[p] for p in PEERS[i]}
    return [d for d in range(1, 10) if d not in used]

def conflicts(grid):
    """Cells whose digit is repeated among their peers."""
    return [i for i in range(81) if grid[i] and any(grid[p] == grid[i] for p in PEERS[i])]
Python Peers, candidates and conflicts

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 input()), it gets the next line from this box.

Cell 2 can only be a 1, 2 or 4 given its neighbors. The red highlighting in the GUI will simply paint every cell returned by conflicts.

Solving by backtracking

Backtracking is "try a digit, continue, and if you get stuck, undo and try the next". Naively it works but can be slow. The standard improvement is the most constrained cell (minimum remaining values) heuristic: always fill the empty cell with the fewest candidates. Cells with one candidate are forced moves, and a cell with zero candidates means the current branch is a dead end, so we backtrack right away.

Python
def solve(grid, limit=1, order=None):
    """Return a list of up to `limit` solved grids (grid is not modified)."""
    solutions = []
    work = grid[:]

    def search():
        if len(solutions) >= limit:
            return
        best, best_c = None, None
        for i in range(81):
            if work[i] == 0:
                c = candidates(work, i)
                if best is None or len(c) < len(best_c):
                    best, best_c = i, c
                    if len(c) <= 1:
                        break
        if best is None:                       # no empty cells: solved
            solutions.append(work[:])
            return
        if order:
            order(best_c)                      # e.g. random.shuffle for generation
        for d in best_c:
            work[best] = d
            search()
            if len(solutions) >= limit:
                return
        work[best] = 0                         # undo
    search()
    return solutions

With limit=2 the function tells you whether a puzzle has one solution or more than one, which is exactly what a generator needs.

Python Solve a puzzle and count solutions

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 input()), it gets the next line from this box.

Generating a puzzle

A generator works in two phases:

  1. Make a full valid grid by solving an empty grid with the candidates in random order.
  2. Remove digits one by one in random order. After each removal check that the puzzle still has exactly one solution (solve(..., limit=2) returns one grid); if it does not, put the digit back.

Fewer givens means a harder puzzle; common targets are about 40 givens for easy, 32 for medium and 26 or fewer for hard.

Python Generate a puzzle with a unique solution

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 input()), it gets the next line from this box.

Because uniqueness is checked at every removal, any puzzle you ship has exactly one answer, which is a promise players care about.

The GUI

The window draws a 9 by 9 grid with thicker lines every third cell, highlights the selected cell and its row, column and box, shows givens in a bolder colour and flags conflicts in red.

Python
import random
import pygame
from sudoku_logic import PEERS, conflicts, generate, solve   # the code above in sudoku_logic.py

pygame.init()
CELL, MARGIN = 60, 30
SIZE = CELL * 9 + MARGIN * 2
screen = pygame.display.set_mode((SIZE, SIZE + 50))
pygame.display.set_caption("Sudoku")
font = pygame.font.Font(None, 48)
small = pygame.font.Font(None, 28)
clock = pygame.time.Clock()

rng = random.Random()
puzzle, solution = generate(36, rng)
grid = puzzle[:]
given = [v != 0 for v in puzzle]
selected = None
message = "Click a cell, type 1-9. Backspace clears. H = hint."

def cell_at(pos):
    x, y = pos[0] - MARGIN, pos[1] - MARGIN
    if 0 <= x < CELL * 9 and 0 <= y < CELL * 9:
        return (y // CELL) * 9 + x // CELL
    return None

running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.MOUSEBUTTONDOWN and event.button == 1:
            selected = cell_at(event.pos)
        elif event.type == pygame.KEYDOWN and selected is not None and not given[selected]:
            if pygame.K_1 <= event.key <= pygame.K_9:
                grid[selected] = event.key - pygame.K_0
            elif event.key in (pygame.K_BACKSPACE, pygame.K_DELETE, pygame.K_0):
                grid[selected] = 0
            elif event.key == pygame.K_h:
                grid[selected] = solution[selected]
        elif event.type == pygame.KEYDOWN and event.key == pygame.K_n:
            puzzle, solution = generate(36, rng)
            grid, given, selected = puzzle[:], [v != 0 for v in puzzle], None

    bad = set(conflicts(grid))
    solved = 0 not in grid and not bad

    screen.fill((250, 250, 252))
    if selected is not None:
        for i in PEERS[selected] | {selected}:
            r, c = divmod(i, 9)
            tint = (200, 220, 255) if i == selected else (232, 238, 250)
            pygame.draw.rect(screen, tint, (MARGIN + c * CELL, MARGIN + r * CELL, CELL, CELL))
    for i, v in enumerate(grid):
        if v:
            r, c = divmod(i, 9)
            colour = (200, 40, 40) if i in bad else (20, 20, 30) if given[i] else (30, 90, 200)
            img = font.render(str(v), True, colour)
            screen.blit(img, img.get_rect(center=(MARGIN + c * CELL + CELL // 2, MARGIN + r * CELL + CELL // 2)))
    for k in range(10):
        w = 4 if k % 3 == 0 else 1
        pygame.draw.line(screen, (30, 30, 40), (MARGIN + k * CELL, MARGIN), (MARGIN + k * CELL, MARGIN + 9 * CELL), w)
        pygame.draw.line(screen, (30, 30, 40), (MARGIN, MARGIN + k * CELL), (MARGIN + 9 * CELL, MARGIN + k * CELL), w)
    text = "Solved! Press N for a new puzzle" if solved else message
    screen.blit(small.render(text, True, (60, 60, 80)), (MARGIN, SIZE + 10))
    pygame.display.flip()
    clock.tick(60)
pygame.quit()

Generating a puzzle takes a moment in pure Python (a fraction of a second on a modern machine). To avoid a visible freeze, generate the next puzzle in a background thread, or pre-generate one while the player is solving.

Improvements worth trying

  • Pencil marks: store a set of candidate digits per cell and draw them tiny in a 3 by 3 pattern inside the cell.
  • Difficulty menu that passes a different givens_target.
  • Timer and best times saved with JSON.
  • Undo and redo with a list of moves.
  • Smart hints: look for a cell with exactly one candidate ("naked single") and highlight it instead of revealing the answer.
  • Keyboard navigation with the arrow keys, as in a spreadsheet.
  • Check the player's grid against the solution and show a mistake counter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a list of 81 cells, which formula gives the row of cell i?

    Integer division by 9 gives the row; i % 9 gives the column.
  2. 2. How many peers does each cell have?

    8 in the row, 8 in the column and 4 more in the box (those not already in the row or column).
  3. 3. Why does the solver pick the empty cell with the fewest candidates?

    This 'minimum remaining values' heuristic prunes the search tree dramatically.
  4. 4. How does the generator make sure a puzzle has one solution?

    Stopping the search at two solutions is a cheap uniqueness test; if a removal creates two, the digit is restored.

Summary

  • Model the board as 81 integers, with precomputed peers for fast rule checks.
  • Conflicts and candidates come from comparing a cell with its 20 peers.
  • A backtracking solver with the most-constrained-cell heuristic is fast, and limit=2 tests uniqueness.
  • A generator makes a random full grid and removes digits while keeping the solution unique.
  • The GUI maps clicks to cells, highlights peers, shows conflicts and accepts digit keys.

Next: Platformer Game