Lesson 23: Puzzle Games

🧩 What Makes a Puzzle Game

Play first. Swap two neighboring gems to make a line of three, and watch what happens after the first match clears. Then switch to the sliding puzzle and try to put the tiles back in order.

Strip away the art and every puzzle game has the same three parts:

1. State: the board. For grid puzzles that's a 2D list, grid[row][col], holding small integers: a gem color from 0 to 5, a tile number from 1 to 15, and a special value for "empty".
2. Rules: which moves are legal and what happens after one. For match-3: swap neighbors, clear lines, drop, refill. For sliding: move a tile into the gap.
3. Goal: a check that says won or lost. For Gem Swap: reach the target score before you run out of moves.

This lesson keeps the rules in plain functions that take the grid and change it, separate from the pygame code that draws it and reads the mouse. That split is the most useful habit in puzzle programming: you can test find_matches(grid) with a hand-made grid in a few lines, without opening a window.

The game's own state (playing, won, lost) is a small Enum, just like the scene states in the Game States & Scenes lesson:

class State(Enum):
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"

Compare that with plain strings: if state == "plaing": is simply never true and fails silently, and a dictionary lookup with a mistyped key, scores["plaing"], raises KeyError (while scores.get("plaing") quietly returns None). A mistyped Enum member, State.PLAING, raises AttributeError the moment that line runs, which points you straight at the typo.

💎 Match-3: Finding Matches

A match is a run: three or more equal gems next to each other in a row or a column. The cleanest way to find runs is to walk along each row, measure how far the current color continues, and record the run if it is at least three long. Then do the same down each column. Collecting the cells in a set means a gem that is part of both a row and a column match (an L or T shape) is counted once.

ROWS, COLS = 8, 8
EMPTY = -1


def find_matches(grid):
    """Return the set of (row, col) cells that are part of a line of 3 or more."""
    matched = set()
    for r in range(ROWS):                # horizontal runs
        c = 0
        while c < COLS:
            end = c
            while end + 1 < COLS and grid[r][end + 1] == grid[r][c]:
                end += 1
            if grid[r][c] != EMPTY and end - c + 1 >= 3:
                matched.update((r, k) for k in range(c, end + 1))
            c = end + 1
    for c in range(COLS):                # vertical runs
        r = 0
        while r < ROWS:
            end = r
            while end + 1 < ROWS and grid[end + 1][c] == grid[r][c]:
                end += 1
            if grid[r][c] != EMPTY and end - r + 1 >= 3:
                matched.update((k, c) for k in range(r, end + 1))
            r = end + 1
    return matched

Notice the check for EMPTY: three empty cells in a row are not a match. To turn a mouse click into a cell, subtract the board's top-left corner and divide by the cell size, then make sure the result is on the board:

def cell_at(pos):
    """Screen pixel -> (row, col), or None outside the board."""
    col = (pos[0] - BOARD_X) // CELL
    row = (pos[1] - BOARD_Y) // CELL
    if 0 <= row < ROWS and 0 <= col < COLS:
        return int(row), int(col)
    return None

Watch the order: a cell is (row, col), and row comes from the y coordinate. Mixing up x/y and row/col is the most common grid bug there is.

🔁 Swaps, Gravity and Cascades

In a match-3 game a swap only counts if it makes a match. The easiest way to know is to try it: swap, look for matches, and swap back if there are none.

def swap(grid, a, b):
    (r1, c1), (r2, c2) = a, b
    grid[r1][c1], grid[r2][c2] = grid[r2][c2], grid[r1][c1]


def are_adjacent(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1]) == 1


def try_swap(grid, a, b):
    """Swap two neighbors. Keep the swap only if it makes a match."""
    if not are_adjacent(a, b):
        return False
    swap(grid, a, b)
    if find_matches(grid):
        return True
    swap(grid, a, b)                     # no match: put them back
    return False

After matched gems are set to EMPTY, gravity pulls the survivors down. Working one column at a time, collect the gems that are left (top to bottom, so they keep their order), and put the right number of empties above them. Then refill the empties with new random gems.

def collapse(grid):
    """Let gems fall: each column keeps its gems in order, empties go to the top."""
    for c in range(COLS):
        gems = [grid[r][c] for r in range(ROWS) if grid[r][c] != EMPTY]
        column = [EMPTY] * (ROWS - len(gems)) + gems
        for r in range(ROWS):
            grid[r][c] = column[r]


def refill(grid, rng):
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == EMPTY:
                grid[r][c] = rng.randrange(GEM_TYPES)

New gems can land in a line, so one swap can set off a chain of matches, called a cascade. Cascades are where the excitement comes from, so each level is worth more: the first clear scores 10 per gem, the second 20, the third 30. The resolver repeats clear, drop and refill until the board is stable:

def resolve(grid, rng):
    """Clear, drop and refill until the board is stable. Return (points, cascades)."""
    points = cascades = 0
    while True:
        matched = find_matches(grid)
        if not matched:
            return points, cascades
        cascades += 1
        points += len(matched) * 10 * cascades     # each cascade level is worth more
        for r, c in matched:
            grid[r][c] = EMPTY
        collapse(grid)
        refill(grid, rng)

How long do cascades get in practice? We measured it with this lesson's code: on 2,000 random 8 × 8 boards with six colors, the first legal swap produced a single clear 1,590 times, two levels 309 times, and the longest chain was 7 levels. Chains are usually short, but not always.

🚧 No Dead Boards

Two situations ruin a match-3 game: the board starts with matches already on it (free points nobody earned), or the player has no legal move left and is stuck forever. Both are fixable.

A clean start. Fill the board cell by cell, left to right and top to bottom. Before picking a color, remove the one that would complete a line with the two gems to the left, and the one that would complete a line with the two gems above:

def new_board(rng):
    """A random board with no matches already on it and at least one move."""
    while True:
        grid = [[EMPTY] * COLS for _ in range(ROWS)]
        for r in range(ROWS):
            for c in range(COLS):
                choices = list(range(GEM_TYPES))
                if c >= 2 and grid[r][c - 1] == grid[r][c - 2]:
                    choices.remove(grid[r][c - 1])
                if r >= 2 and grid[r - 1][c] == grid[r - 2][c] and grid[r - 1][c] in choices:
                    choices.remove(grid[r - 1][c])
                grid[r][c] = rng.choice(choices)
        if has_possible_move(grid):
            return grid

At least one move. To find out whether a move exists, try every swap of a gem with its right and lower neighbor, check for a match, and swap back. 8 × 8 is only 112 swaps, which is quick enough to check after every turn.

def has_possible_move(grid):
    """True if at least one swap of neighbors would make a match."""
    for r in range(ROWS):
        for c in range(COLS):
            for b in ((r, c + 1), (r + 1, c)):
                if b[0] < ROWS and b[1] < COLS:
                    swap(grid, (r, c), b)
                    found = bool(find_matches(grid))
                    swap(grid, (r, c), b)
                    if found:
                        return True
    return False

A fair reshuffle. When no move is left, rearrange the same gems. A random shuffle might create matches or still have no move, so keep shuffling until both conditions hold, with a fresh board as a last resort so the loop always ends:

def shuffle_until_playable(grid, rng):
    """Rearrange the same gems until there is no match on the board and a move exists."""
    gems = [gem for row in grid for gem in row]
    for _ in range(200):
        rng.shuffle(gems)
        for i, gem in enumerate(gems):
            grid[i // COLS][i % COLS] = gem
        if not find_matches(grid) and has_possible_move(grid):
            return
    grid[:] = new_board(rng)             # extremely unlucky: start a fresh board

Every function takes an rng, a random.Random(seed) instance, as in the Randomness for Games lesson. The same seed gives the same boards, which makes bugs repeatable and lets you design fixed "daily puzzles".

🔢 Sliding Puzzles and Solvability

The 15-puzzle is a 4 × 4 frame with tiles 1 to 15 and one gap. You slide a tile next to the gap into it, and win when the tiles are back in order. It hides a famous trap: if you place the tiles in a random order, exactly half of all arrangements can never be solved, no matter how you slide. Swap just the 14 and 15 of a solved puzzle and you have one of them.

There are two ways to stay safe:

• Shuffle with legal moves. Start from the solved board and make a few hundred random slides. Every slide can be undone, so the board can always be solved by reversing them. This is what the program below does.
• Test with the parity rule. Read the tiles left to right, top to bottom (skipping the gap) and count the inversions: pairs where a larger number comes before a smaller one. On a board with an odd width, the puzzle is solvable exactly when that count is even. On an even width like 4 × 4, also count the gap's row from the bottom (1 = bottom row): the puzzle is solvable exactly when inversions plus that row number is odd.

Here is a complete sliding puzzle. Click a tile next to the gap, or use the arrow keys to push a tile into it.

"""Sliding Puzzle: Intermediate Lesson 23 worked example.

Click a tile next to the gap (or press an arrow key) to slide it.
Put the tiles back in order 1-15 with the gap in the bottom-right corner.
R shuffles a new puzzle.
"""
import random

import pygame


SIZE = 4
TILE = 90
TOP = 60                                  # room for the HUD above the board
WIDTH, HEIGHT = SIZE * TILE, TOP + SIZE * TILE
BLANK = 0


def solved_board():
    board = [[r * SIZE + c + 1 for c in range(SIZE)] for r in range(SIZE)]
    board[SIZE - 1][SIZE - 1] = BLANK
    return board


def find_blank(board):
    for r in range(SIZE):
        for c in range(SIZE):
            if board[r][c] == BLANK:
                return r, c
    return None


def slide(board, row, col):
    """Slide the tile at (row, col) into the gap if they are neighbors."""
    br, bc = find_blank(board)
    if abs(br - row) + abs(bc - col) != 1:
        return False
    board[br][bc], board[row][col] = board[row][col], BLANK
    return True


def shuffle(board, rng, moves=300):
    """Scramble with random LEGAL slides, so the puzzle can always be solved."""
    for _ in range(moves):
        br, bc = find_blank(board)
        options = [(br + dr, bc + dc) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
                   if 0 <= br + dr < SIZE and 0 <= bc + dc < SIZE]
        slide(board, *rng.choice(options))


def is_solved(board):
    return board == solved_board()


def is_solvable(board):
    """The classic parity test: works for any board, however it was made."""
    tiles = [t for row in board for t in row if t != BLANK]
    inversions = sum(1 for i in range(len(tiles)) for j in range(i + 1, len(tiles))
                     if tiles[i] > tiles[j])
    if SIZE % 2 == 1:
        return inversions % 2 == 0
    blank_row_from_bottom = SIZE - find_blank(board)[0]
    return (inversions + blank_row_from_bottom) % 2 == 1


def main():
    pygame.init()
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    pygame.display.set_caption("Sliding Puzzle")
    clock = pygame.time.Clock()
    font = pygame.font.Font(None, 48)
    hud_font = pygame.font.Font(None, 28)
    labels = {n: font.render(str(n), True, (20, 24, 36)) for n in range(1, SIZE * SIZE)}
    rng = random.Random(15)
    board = solved_board()
    shuffle(board, rng)
    moves = 0
    # Pressing an arrow slides the tile on the OTHER side of the gap toward it.
    arrow_offsets = {pygame.K_LEFT: (0, 1), pygame.K_RIGHT: (0, -1),
                     pygame.K_UP: (1, 0), pygame.K_DOWN: (-1, 0)}

    running = True
    while running:
        clock.tick(60)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.MOUSEBUTTONDOWN and event.button == 1 and not is_solved(board):
                col, row = event.pos[0] // TILE, (event.pos[1] - TOP) // TILE
                if 0 <= row < SIZE and 0 <= col < SIZE and slide(board, row, col):
                    moves += 1
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_r:
                    shuffle(board, rng)
                    moves = 0
                elif event.key in arrow_offsets and not is_solved(board):
                    br, bc = find_blank(board)
                    dr, dc = arrow_offsets[event.key]
                    if 0 <= br + dr < SIZE and 0 <= bc + dc < SIZE and slide(board, br + dr, bc + dc):
                        moves += 1

        screen.fill((24, 26, 40))
        status = "Solved!  R for a new puzzle" if is_solved(board) else f"Moves: {moves}"
        screen.blit(hud_font.render(status, True, (235, 235, 235)), (12, 20))
        for r in range(SIZE):
            for c in range(SIZE):
                if board[r][c] != BLANK:
                    rect = pygame.Rect(c * TILE, TOP + r * TILE, TILE, TILE).inflate(-6, -6)
                    pygame.draw.rect(screen, (240, 200, 110), rect, border_radius=10)
                    label = labels[board[r][c]]
                    screen.blit(label, label.get_rect(center=rect.center))
        pygame.display.flip()

    pygame.quit()
    print(f"Moves: {moves}. Solved: {is_solved(board)}. Solvable: {is_solvable(board)}.")


if __name__ == "__main__":
    main()

🏋️ Practice Exercise: Gem Swap

"""Gem Swap: Intermediate Lesson 23 practice exercise (solution).

A match-3 game: click a gem, then click a neighbor to swap them. A swap only
counts if it makes a line of 3 or more; matches clear, gems fall, new gems
drop in and cascades multiply the score. Reach the target score before you
run out of moves. R starts a new game.
"""
import random
from enum import Enum

import pygame


ROWS, COLS = 8, 8
GEM_TYPES = 6
EMPTY = -1
CELL = 48
BOARD_X, BOARD_Y = 40, 110               # the HUD lives above the board, never on it
WIDTH, HEIGHT = BOARD_X * 2 + COLS * CELL, BOARD_Y + ROWS * CELL + 30
MOVES = 20
TARGET = 1500
GEM_COLORS = [(235, 80, 80), (80, 200, 110), (80, 140, 235),
              (240, 210, 80), (190, 100, 220), (80, 210, 220)]
TEXT_COLOR = (235, 235, 235)


class State(Enum):
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"


# ---------- the model: plain functions on grid[row][col] ----------

def find_matches(grid):
    """Return the set of (row, col) cells that are part of a line of 3 or more."""
    matched = set()
    for r in range(ROWS):                # horizontal runs
        c = 0
        while c < COLS:
            end = c
            while end + 1 < COLS and grid[r][end + 1] == grid[r][c]:
                end += 1
            if grid[r][c] != EMPTY and end - c + 1 >= 3:
                matched.update((r, k) for k in range(c, end + 1))
            c = end + 1
    for c in range(COLS):                # vertical runs
        r = 0
        while r < ROWS:
            end = r
            while end + 1 < ROWS and grid[end + 1][c] == grid[r][c]:
                end += 1
            if grid[r][c] != EMPTY and end - r + 1 >= 3:
                matched.update((k, c) for k in range(r, end + 1))
            r = end + 1
    return matched


def swap(grid, a, b):
    (r1, c1), (r2, c2) = a, b
    grid[r1][c1], grid[r2][c2] = grid[r2][c2], grid[r1][c1]


def are_adjacent(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1]) == 1


def try_swap(grid, a, b):
    """Swap two neighbors. Keep the swap only if it makes a match."""
    if not are_adjacent(a, b):
        return False
    swap(grid, a, b)
    if find_matches(grid):
        return True
    swap(grid, a, b)                     # no match: put them back
    return False


def collapse(grid):
    """Let gems fall: each column keeps its gems in order, empties go to the top."""
    for c in range(COLS):
        gems = [grid[r][c] for r in range(ROWS) if grid[r][c] != EMPTY]
        column = [EMPTY] * (ROWS - len(gems)) + gems
        for r in range(ROWS):
            grid[r][c] = column[r]


def refill(grid, rng):
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == EMPTY:
                grid[r][c] = rng.randrange(GEM_TYPES)


def resolve(grid, rng):
    """Clear, drop and refill until the board is stable. Return (points, cascades)."""
    points = cascades = 0
    while True:
        matched = find_matches(grid)
        if not matched:
            return points, cascades
        cascades += 1
        points += len(matched) * 10 * cascades     # each cascade level is worth more
        for r, c in matched:
            grid[r][c] = EMPTY
        collapse(grid)
        refill(grid, rng)


def has_possible_move(grid):
    """True if at least one swap of neighbors would make a match."""
    for r in range(ROWS):
        for c in range(COLS):
            for b in ((r, c + 1), (r + 1, c)):
                if b[0] < ROWS and b[1] < COLS:
                    swap(grid, (r, c), b)
                    found = bool(find_matches(grid))
                    swap(grid, (r, c), b)
                    if found:
                        return True
    return False


def new_board(rng):
    """A random board with no matches already on it and at least one move."""
    while True:
        grid = [[EMPTY] * COLS for _ in range(ROWS)]
        for r in range(ROWS):
            for c in range(COLS):
                choices = list(range(GEM_TYPES))
                if c >= 2 and grid[r][c - 1] == grid[r][c - 2]:
                    choices.remove(grid[r][c - 1])
                if r >= 2 and grid[r - 1][c] == grid[r - 2][c] and grid[r - 1][c] in choices:
                    choices.remove(grid[r - 1][c])
                grid[r][c] = rng.choice(choices)
        if has_possible_move(grid):
            return grid


def shuffle_until_playable(grid, rng):
    """Rearrange the same gems until there is no match on the board and a move exists."""
    gems = [gem for row in grid for gem in row]
    for _ in range(200):
        rng.shuffle(gems)
        for i, gem in enumerate(gems):
            grid[i // COLS][i % COLS] = gem
        if not find_matches(grid) and has_possible_move(grid):
            return
    grid[:] = new_board(rng)             # extremely unlucky: start a fresh board


def cell_at(pos):
    """Screen pixel -> (row, col), or None outside the board."""
    col = (pos[0] - BOARD_X) // CELL
    row = (pos[1] - BOARD_Y) // CELL
    if 0 <= row < ROWS and 0 <= col < COLS:
        return int(row), int(col)
    return None


# ---------- the game: state, input, drawing ----------

class Game:
    def __init__(self, seed=None):
        self.rng = random.Random(seed)
        self.restart()

    def restart(self):
        self.grid = new_board(self.rng)
        self.selected = None
        self.score = 0
        self.moves_left = MOVES
        self.state = State.PLAYING
        self.message = ""
        self.message_timer = 0.0

    def say(self, text, seconds=1.2):
        self.message, self.message_timer = text, seconds

    def click(self, cell):
        if self.state is not State.PLAYING or cell is None:
            return
        if self.selected is None or not are_adjacent(self.selected, cell):
            self.selected = cell
            return
        a, self.selected = self.selected, None
        if not try_swap(self.grid, a, cell):
            self.say("No match: swap undone")
            return
        self.moves_left -= 1
        points, cascades = resolve(self.grid, self.rng)
        self.score += points
        if cascades > 1:
            self.say(f"Cascade x{cascades}!  +{points}")
        if not has_possible_move(self.grid):
            shuffle_until_playable(self.grid, self.rng)
            self.say("No moves left: shuffled")
        if self.score >= TARGET:
            self.state = State.WON
        elif self.moves_left == 0:
            self.state = State.LOST

    def update(self, dt):
        self.message_timer = max(0.0, self.message_timer - dt)

    def draw(self, screen, font, big_font):
        screen.fill((24, 26, 40))
        hud = f"Score {self.score} / {TARGET}     Moves {self.moves_left}"
        screen.blit(font.render(hud, True, TEXT_COLOR), (BOARD_X, 20))
        if self.message_timer > 0:
            screen.blit(font.render(self.message, True, (255, 220, 120)), (BOARD_X, 52))
        for r in range(ROWS):
            for c in range(COLS):
                cell = pygame.Rect(BOARD_X + c * CELL, BOARD_Y + r * CELL, CELL, CELL)
                pygame.draw.rect(screen, (38, 42, 62), cell.inflate(-2, -2), border_radius=6)
                gem = self.grid[r][c]
                if gem != EMPTY:
                    pygame.draw.circle(screen, GEM_COLORS[gem], cell.center, CELL // 2 - 6)
                if self.selected == (r, c):
                    pygame.draw.rect(screen, (255, 255, 255), cell, 3, border_radius=6)
        if self.state is not State.PLAYING:
            text = "You win!" if self.state is State.WON else "Out of moves"
            label = big_font.render(f"{text}  (R to restart)", True, TEXT_COLOR)
            screen.blit(label, label.get_rect(center=(WIDTH / 2, BOARD_Y - 26)))


def main():
    pygame.init()
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    pygame.display.set_caption("Gem Swap")
    clock = pygame.time.Clock()
    font = pygame.font.Font(None, 28)
    big_font = pygame.font.Font(None, 34)
    game = Game(seed=23)

    running = True
    while running:
        dt = clock.tick(60) / 1000
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.MOUSEBUTTONDOWN and event.button == 1:
                game.click(cell_at(event.pos))
            elif event.type == pygame.KEYDOWN and event.key == pygame.K_r:
                game.restart()
        game.update(dt)
        game.draw(screen, font, big_font)
        pygame.display.flip()

    pygame.quit()
    print(f"Score: {game.score}. Moves left: {game.moves_left}. State: {game.state.value}.")


if __name__ == "__main__":
    main()

📓 Learning Journal

📝 Summary

You treated puzzles as what they really are: a grid of small numbers and a few rules. Match-3 became a chain of small, testable functions: find runs, try a swap and undo it if it fails, let gems fall, refill, and loop until the board is stable, with each cascade level worth more. You made sure players always get a fair board, with no free matches at the start and a reshuffle when they're stuck. Finally, you saw that half of all sliding-puzzle arrangements are unsolvable, and how legal-move shuffling and the parity rule keep you safe.

🔭 Looking Ahead

Next is RPG Systems, where the "board" becomes a character: you build stats and levels, an inventory with equipment, a dialogue graph, a quest that pays out exactly once, and save files that remember all of it.

❓ Common Questions

🎯 Quick Quiz

🌟 Going Further

• Hint button: make has_possible_move() return the swap it found instead of True, and highlight those two gems when the player presses H.
• Special gems: a run of four leaves a "line bomb" that clears its whole row when matched.
• Falling animation: tween each gem's drawn y position toward its cell, and ignore clicks until the board settles.
• Picture puzzle: cut an image into 16 subsurfaces (as in the Sprite Sheets lesson) and use them as sliding tiles.
• Read the docs: random.Random and Python sets.
• Coming up in Game Dev III: Advanced: Wave Function Collapse generates grids that follow local rules, a close cousin of the match rules you wrote today.