Jigsaw Puzzle — Low Level Design · Engineering Playbook

Context#

A jigsaw puzzle is a grid of interlocking pieces, where each piece has four edges and each edge is either an interior shape (a tab sticking out, or a blank recessed in) or a flat edge that lines the puzzle’s border. Two pieces fit if a tab on one matches a blank on the other in both geometry and the colour/pattern of the underlying image.

This is the lightest case study in the OOD catalogue. There is no transactional state machine, no user roles, no payments. The interview tests two things and two things only: can you model the piece correctly (edges, neighbours, fit predicate), and can you write a backtracking solver that fills the grid one piece at a time and backs out when it gets stuck?

The interviewer’s hidden objectives:

Can you put fits(other, side) on Piece itself, so the solver does not branch on edge types?
Can you keep the solver stateless with respect to the piece set — it should accept any puzzle, not just one shape?
Can you reason about the search space and pick a sensible heuristic (start with a corner, prefer the most-constrained position next)?

Requirements (functional and non-functional)#

This is a deliberately small problem. Be ruthless about scope.

Functional — in scope.

A rectangular puzzle of rows × cols pieces. (Non-rectangular shapes are an extension; flag and skip.)
Each piece has four edges: top, right, bottom, left.
Each edge has a shape — flat, tab, or blank — and an associated pattern (a hash of the image fragment along that edge).
Two pieces fit on a given side if their shapes complement (tab + blank, never tab + tab) and their patterns match.
A puzzle is solved when every grid cell holds a piece that fits its neighbours on every shared edge, and border cells have flat edges on their outward sides.
A solver takes the unsorted set of pieces and returns a fully assembled grid (or reports no solution).
Pieces may need to be rotated to fit. The solver tries all four orientations.

Functional — out of scope (called out explicitly). Visual rendering, pattern recognition from raw pixels (we assume edge-pattern hashes are pre-computed), real-time UI, multi-player solving, partial assistance / hints. These will not be discussed unless added as follow-ups.

Non-functional.

Puzzle sizes up to ~1000 pieces should solve in well under a minute on a single thread. (10000-piece puzzles need the optimisation discussion in trade-offs.)
Determinism: the same input piece set with the same heuristic should yield the same assembly.

Use case diagram#

            ┌────────────┐
            │  Solver    │   (the only actor for this case study)
            └─────┬──────┘
                  │
       ┌──────────┼──────────┐
       ▼          ▼          ▼
   [load pieces] [solve]  [report]
       │          │          │
       └──────────┼──────────┘
                  ▼
   ┌───────────────────────────────┐
   │      Jigsaw Puzzle System     │
   │   (piece model + backtracking)│
   └───────────────────────────────┘

The actor list is intentionally short — this is a solver, not a service. Compared with the Parking Lot or Car Rental writeups, there is no human role to model.

Class diagram#

                  ┌─────────────────────────────────┐
                  │             Puzzle              │
                  ├─────────────────────────────────┤
                  │ rows, cols                      │
                  │ grid : Piece[rows][cols]        │
                  │ available : Set<Piece>          │
                  ├─────────────────────────────────┤
                  │ isSolved()                      │
                  │ place(r, c, piece, rotation)    │
                  │ remove(r, c)                    │
                  └──────────────┬──────────────────┘
                                 │ 1
                                 ▼
                  ┌─────────────────────────────────┐
                  │              Piece              │
                  ├─────────────────────────────────┤
                  │ id                              │
                  │ edges : Edge[4]                 │   // indices: 0=top, 1=right, 2=bottom, 3=left
                  │ rotation : 0 | 90 | 180 | 270   │
                  ├─────────────────────────────────┤
                  │ edge(side) → Edge               │
                  │ rotated(r) → Piece              │
                  │ fits(other, side) → boolean     │
                  │ isCorner() / isEdge() / isInterior() │
                  └──────────────┬──────────────────┘
                                 │ 4
                                 ▼
                  ┌─────────────────────────────────┐
                  │              Edge               │
                  ├─────────────────────────────────┤
                  │ shape : EdgeShape  (FLAT/TAB/BLANK) │
                  │ pattern : long  (hash)          │
                  ├─────────────────────────────────┤
                  │ complements(other) → boolean    │
                  └─────────────────────────────────┘

                  ┌─────────────────────────────────┐
                  │             Solver              │
                  ├─────────────────────────────────┤
                  │ puzzle : Puzzle                 │
                  ├─────────────────────────────────┤
                  │ solve() → boolean               │
                  │ nextCell() → (r,c) | none       │
                  │ candidates(r,c) → Iterable<Piece, Rotation> │
                  └─────────────────────────────────┘

Piece is the load-bearing class. Everything the solver needs — what does this edge look like? what does this corner fit against? — is a method on Piece or on Edge. The solver itself stays slim.

Notice what is not in the diagram:

No subclass per edge shape. A Tab/Blank/Flat hierarchy would mean three classes that hold no behaviour beyond an identity check. EdgeShape is an enum. Edges differ in data (shape and pattern), not in behaviour.
No subclass per piece kind. Corner, edge, and interior pieces are identified by their edge pattern (isCorner = two flat edges, isEdge = one flat edge). A class hierarchy here would mean reclassifying after every rotation.
No Pattern class. The pattern is a long hash — equality is what matters.

Sequence diagram (key flows)#

A trace of the solver running over a small puzzle. We compress the recursion — every call shown stands for many similar calls.

 Caller        Solver           Puzzle           Piece              Edge
   │ solve()      │                │                │                  │
   │─────────────►│                │                │                  │
   │              │ nextCell() ───►│                │                  │
   │              │  (0,0)         │                │                  │
   │              │◄───────────────│                │                  │
   │              │ candidates(0,0)│                │                  │
   │              │────────────────────────────────►│ isCorner()?       │
   │              │                │                │ true / false      │
   │              │                │                │◄──────────────────│
   │              │  corner pieces (4 rotations each)                   │
   │              │ place(0,0, p, r) ──────────────►│                  │
   │              │ recursive solve()              │                  │
   │              │ … (fills (0,1), (0,2)…)         │                  │
   │              │ at some (r,c): no candidates fit                    │
   │              │ remove(r,c) ──►│                │                  │
   │              │ try next candidate at the previous cell             │
   │              │ … until grid is full or all roots exhausted         │
   │ true/false   │                │                │                  │
   │◄─────────────│                │                │                  │

In a 100-piece puzzle the recursion depth is 100; in a 1000-piece puzzle it is 1000. The branching factor at each cell is small if the candidates filter is tight — see the solver code below.

Activity diagram (for non-trivial state)#

The solver’s backtracking is the only non-trivial control flow. Sketching it:

              ┌─────────┐
              │  start  │
              └────┬────┘
                   ▼
            ┌────────────────┐
            │  pick next cell │
            └────┬───────────┘
                 │ none → success
                 ▼
            ┌────────────────────────┐
            │ enumerate candidates    │
            │ (piece, rotation)       │
            └────┬───────────────────┘
                 │
        ┌────────┴────────┐
        ▼                 ▼
   (no candidates)   (try candidate)
        │                 │
   ┌────▼──────┐    ┌─────▼────────┐
   │ backtrack │    │ place piece  │
   └────┬──────┘    │ recurse      │
        │           └─────┬────────┘
        │                 │
        ▼            ┌────▼─────┐
   (return up)       │ solved?  │
                     ├──────────┤
                     │ yes → done│
                     │ no  → remove, try next candidate │
                     └──────────┘

backtrack is implicit in the recursion — when the recursive call returns false, the caller’s loop simply moves to the next candidate. There is no separate “backtrack” routine.

Java implementation#

The complete class skeleton plus a working backtracking solver. The solver below is the focus of the writeup; the other classes are kept short so the recursive logic is the centrepiece.

public enum EdgeShape { FLAT, TAB, BLANK }

public record Edge(EdgeShape shape, long pattern) {
    public boolean complements(Edge other) {
        if (this.shape == EdgeShape.FLAT || other.shape == EdgeShape.FLAT) return false;
        if (this.shape == other.shape) return false;     // tab+tab or blank+blank cannot fit
        return this.pattern == other.pattern;             // tab+blank with matching pattern
    }
}

public final class Piece {
    public static final int TOP = 0, RIGHT = 1, BOTTOM = 2, LEFT = 3;
    private final String id;
    private final Edge[] edges;       // canonical orientation, length 4
    private final int rotation;       // 0, 90, 180, 270

    public Piece(String id, Edge top, Edge right, Edge bottom, Edge left) {
        this(id, new Edge[] { top, right, bottom, left }, 0);
    }
    private Piece(String id, Edge[] edges, int rotation) {
        this.id = id; this.edges = edges; this.rotation = rotation;
    }

    /** Edge currently exposed on the given side, accounting for rotation. */
    public Edge edge(int side) {
        int rotSteps = rotation / 90;     // 0..3
        return edges[(side - rotSteps + 4) % 4];
    }

    /** Returns a piece with the same edges, rotated to the given orientation. */
    public Piece rotated(int newRotation) {
        if (newRotation % 90 != 0) throw new IllegalArgumentException("rotation must be multiple of 90");
        return new Piece(id, edges, ((newRotation % 360) + 360) % 360);
    }

    /** Does `other`'s `oppositeSide(side)` fit our `side`? */
    public boolean fits(Piece other, int side) {
        return this.edge(side).complements(other.edge(oppositeSide(side)));
    }

    public boolean isCorner() {
        int flats = 0;
        for (int s = 0; s < 4; s++) if (edge(s).shape() == EdgeShape.FLAT) flats++;
        return flats == 2;
    }
    public boolean isEdge()     { /* exactly one flat */ return countFlats() == 1; }
    public boolean isInterior() { return countFlats() == 0; }

    private int countFlats() {
        int n = 0; for (int s = 0; s < 4; s++) if (edge(s).shape() == EdgeShape.FLAT) n++;
        return n;
    }

    public String id() { return id; }
    public int rotation() { return rotation; }

    public static int oppositeSide(int side) { return (side + 2) % 4; }
}

public final class Puzzle {
    private final int rows, cols;
    private final Piece[][] grid;
    private final Set<String> placed = new HashSet<>();    // piece ids already on the board

    public Puzzle(int rows, int cols) {
        this.rows = rows; this.cols = cols;
        this.grid = new Piece[rows][cols];
    }

    public int rows() { return rows; }
    public int cols() { return cols; }
    public Piece at(int r, int c) { return grid[r][c]; }

    public boolean canPlace(int r, int c, Piece p) {
        if (placed.contains(p.id())) return false;
        // Border constraint: outward-facing edge must be FLAT on the border.
        if (r == 0        && p.edge(Piece.TOP).shape()    != EdgeShape.FLAT) return false;
        if (r == rows - 1 && p.edge(Piece.BOTTOM).shape() != EdgeShape.FLAT) return false;
        if (c == 0        && p.edge(Piece.LEFT).shape()   != EdgeShape.FLAT) return false;
        if (c == cols - 1 && p.edge(Piece.RIGHT).shape()  != EdgeShape.FLAT) return false;
        // Neighbour constraints: each placed neighbour's facing edge must complement.
        if (r > 0        && grid[r-1][c] != null && !grid[r-1][c].fits(p, Piece.BOTTOM)) return false;
        if (c > 0        && grid[r][c-1] != null && !grid[r][c-1].fits(p, Piece.RIGHT))  return false;
        if (r < rows - 1 && grid[r+1][c] != null && !grid[r+1][c].fits(p, Piece.TOP))    return false;
        if (c < cols - 1 && grid[r][c+1] != null && !grid[r][c+1].fits(p, Piece.LEFT))   return false;
        return true;
    }

    public void place(int r, int c, Piece p)  { grid[r][c] = p; placed.add(p.id()); }
    public void remove(int r, int c)          { placed.remove(grid[r][c].id()); grid[r][c] = null; }
}

public final class Solver {
    private final Puzzle puzzle;
    private final List<Piece> pieces;     // shared pool; we filter at each cell

    public Solver(Puzzle puzzle, List<Piece> pieces) {
        this.puzzle = puzzle; this.pieces = pieces;
    }

    public boolean solve() { return solveFrom(0, 0); }

    /** Row-major traversal; at each cell, try every (piece, rotation) that fits, then recurse. */
    private boolean solveFrom(int r, int c) {
        if (r == puzzle.rows()) return true;                     // ran past the bottom — solved
        int nr = (c + 1 == puzzle.cols()) ? r + 1 : r;
        int nc = (c + 1 == puzzle.cols()) ? 0     : c + 1;

        for (Piece p : pieces) {
            for (int rot = 0; rot < 360; rot += 90) {
                Piece oriented = p.rotated(rot);
                if (!puzzle.canPlace(r, c, oriented)) continue;
                puzzle.place(r, c, oriented);
                if (solveFrom(nr, nc)) return true;
                puzzle.remove(r, c);
            }
        }
        return false;
    }
}

Notes interviewers reward:

canPlace packages every constraint — border flatness and neighbour compatibility. The solver does not duplicate any of these checks.
Row-major traversal is a deliberate choice. It guarantees that when we reach cell (r, c), the neighbours above and to the left are already placed, so canPlace rejects bad candidates immediately. A naive solver that scans randomly would do far more wasted work.
Piece.rotated(rot) returns a new view, not a mutated piece. This keeps backtracking simple — there is nothing to undo on the piece itself.
The placed set on Puzzle prevents re-using the same piece without scanning the grid each time.
No subclassing. Corner/edge/interior is a query on Piece, not a type.

The basic search above is exponential in the worst case. The practical speedup comes from a tighter nextCell heuristic — see the trade-offs section.

Trade-offs and extensions#

Decision	Why	Cost if requirements change
`EdgeShape` as an enum	Three values, no per-shape behaviour beyond data carriage	None
Row-major traversal	Easy to reason; neighbours pre-pinned by the time we reach a cell	Worst-case branching for 10000-piece puzzles; prefer most-constrained next
Backtracking with no memoisation	Pieces and positions are unique; subproblems do not repeat	None — DP does not apply to this shape
`Piece.rotated(rot)` returns a new instance	Immutable pieces; trivial backtrack	Tiny allocation overhead; pool if profiling demands
Pattern equality by hash	Cheap O(1) compare; sufficient when patterns are pre-extracted	False positives possible at very small hash sizes — use a wider hash
In-process `List<Piece>` pool	Within scope	If the puzzle is enormous, pre-index pieces by `(side, shape, pattern)` for O(1) candidate lookup

Likely follow-up extensions:

Most-constrained-variable heuristic. Replace row-major with: at each step, pick the empty cell with the fewest legal candidates. Borders and corners come out first naturally. Implement as a priority queue over empty cells, re-scored after each placement.
Constraint propagation. After placing a piece, propagate its constraints to neighbouring empty cells — eliminate candidates upfront. Reduces branching dramatically on hard puzzles.
Cluster-first. Solve obvious sub-clusters (a border ring, a colour-distinctive region) independently, then join. Composite pattern enters here: a cluster implements Placeable.
Parallel solver. Partition by quadrant; solve each in parallel; reconcile at the seams. Adds significant control flow but pays off above ~5000 pieces.
Non-rectangular puzzles. Generalise Puzzle from a grid to a graph of cell positions. The solver becomes a graph-colouring backtracker; the Piece model is unchanged.

Mock interview follow-ups#

“Why not a class hierarchy for corner / edge / interior pieces?” — Identity is data-driven, not behavioural. After a rotation, an interior piece does not become a corner; the position is a corner, the piece has flat edges. Conflating them invites bugs.
“What’s the complexity of the solver?” — Worst case exponential in piece count. In practice the border constraint and pattern matching prune aggressively; a 100-piece puzzle solves in milliseconds, a 1000-piece puzzle in seconds with the most-constrained heuristic.
“How would you handle pieces that match by colour but not by shape?” — That is the visual-pattern extension; the Edge.pattern field already supports it. Tighten the hash or replace with a perceptual comparison.
“Where does Composite fit?” — At the cluster-first extension: a solved sub-region is itself a Placeable with its own outer edges. The solver treats clusters and pieces uniformly.
“What if pieces can be flipped (mirrored)?” — Add a flipped flag alongside rotation. The solver doubles its branching at each cell; constraint pruning compensates.
“How is this different from Sudoku?” — Same backtracking shape, different fit predicate. Sudoku has nine candidates per cell with a simple “no duplicate in row/col/box” rule; jigsaw has many candidates per cell with a geometric and visual rule. The solver template is identical.

Chess Game — the closest neighbour by class shape (board + pieces) even though the game logic is wholly different.
Composite Pattern — the lens for the cluster-first optimisation.
Approaching the OOD Interview — the meta-script that shaped this writeup.
Class Diagrams — the diagram conventions used above.
Polymorphism — why EdgeShape is an enum and not a class hierarchy.