LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 37 OF 42

Design a Jigsaw Puzzle: Low-Level Design in Java

A modelling and algorithm round in one: pieces with four edges (flat, tab, blank) and shapes that must match, rotation as a property of a placement, a board that checks every fit, an edge index that finds the matching piece in O(1) instead of trying them all, a solver that builds the border then fills row by row, hints, multiplayer safety and the follow-ups, with a full Java 17 solution.

Patterns usedObserverStrategyTemplate method

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 23

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 405 lines, with a small main() demo. Save it as JigsawPuzzle.java, then run javac JigsawPuzzle.java && java JigsawPuzzle.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;

/** A jigsaw puzzle: pieces with four edges, a board that checks every fit, and a fast indexed solver. */
public class JigsawPuzzle {

    // ---------- edges and pieces ----------
    /** Clockwise order matters: turning a piece once moves TOP to RIGHT, RIGHT to BOTTOM, and so on. */
    enum Side {
        TOP(-1, 0), RIGHT(0, 1), BOTTOM(1, 0), LEFT(0, -1);

        final int dr, dc;

        Side(int dr, int dc) {
            this.dr = dr;
            this.dc = dc;
        }

        Side opposite() { return values()[(ordinal() + 2) % 4]; }
    }

    enum EdgeType { FLAT, TAB, BLANK }

    /** A tab with shape 7 fits only a blank with shape 7. Flat edges sit on the outside of the puzzle. */
    record Edge(EdgeType type, int shape) {
        static final Edge FLAT = new Edge(EdgeType.FLAT, 0);

        /** The edge that would lock into this one. */
        Edge partner() {
            return switch (type) {
                case TAB -> new Edge(EdgeType.BLANK, shape);
                case BLANK -> new Edge(EdgeType.TAB, shape);
                case FLAT -> throw new IllegalStateException("a flat edge has no partner");
            };
        }

        boolean fits(Edge other) { return type != EdgeType.FLAT && partner().equals(other); }

        @Override
        public String toString() { return type == EdgeType.FLAT ? "F" : type.name().charAt(0) + "" + shape; }
    }

    /** Edges are stored TOP, RIGHT, BOTTOM, LEFT as the piece lies in the box. */
    record Piece(int id, List<Edge> edges) {
        Piece {
            if (edges.size() != 4) throw new IllegalArgumentException("a piece has four edges");
            edges = List.copyOf(edges);
        }

        int flats() {
            int n = 0;
            for (Edge e : edges) if (e.type() == EdgeType.FLAT) n++;
            return n;
        }

        /** The same piece turned clockwise k quarter turns (used to scramble the box). */
        Piece turned(int k) {
            Edge[] out = new Edge[4];
            for (int i = 0; i < 4; i++) out[(i + k) % 4] = edges.get(i);
            return new Piece(id, List.of(out));
        }
    }

    /** A piece on the board, turned clockwise by rotation quarter turns. */
    record Placement(Piece piece, int rotation) {
        Edge edge(Side s) { return piece.edges().get((s.ordinal() - rotation + 4) % 4); }
    }

    // ---------- the board ----------
    interface BoardListener { void placed(int row, int col, Placement p, int placedCount); }

    static final class Board {
        final int rows, cols;
        private final Placement[][] grid;
        private final Set<Integer> used = new HashSet<>();
        private final List<BoardListener> listeners = new CopyOnWriteArrayList<>();
        private long fitChecks;

        Board(int rows, int cols) {
            if (rows < 2 || cols < 2) throw new IllegalArgumentException("need at least 2 x 2");
            this.rows = rows;
            this.cols = cols;
            this.grid = new Placement[rows][cols];
        }

        void subscribe(BoardListener l) { listeners.add(l); }

        boolean inside(int r, int c) { return r >= 0 && r < rows && c >= 0 && c < cols; }

        synchronized Placement at(int r, int c) { return inside(r, c) ? grid[r][c] : null; }

        synchronized boolean isUsed(int pieceId) { return used.contains(pieceId); }

        /** Each side must be flat on the outside, lock into a placed neighbour, or face an empty cell. */
        synchronized boolean canPlace(int r, int c, Placement p) {
            fitChecks++;
            if (!inside(r, c) || grid[r][c] != null || used.contains(p.piece().id())) return false;
            for (Side s : Side.values()) {
                Edge mine = p.edge(s);
                int nr = r + s.dr, nc = c + s.dc;
                if (!inside(nr, nc)) {
                    if (mine.type() != EdgeType.FLAT) return false; // the border must be straight
                } else if (mine.type() == EdgeType.FLAT) {
                    return false; // a flat edge can never face inwards
                } else if (grid[nr][nc] != null && !mine.fits(grid[nr][nc].edge(s.opposite()))) {
                    return false;
                }
            }
            return true;
        }

        /** Check and place in one locked step, so two players can never fill the same cell. */
        synchronized void place(int r, int c, Placement p) {
            if (!canPlace(r, c, p))
                throw new IllegalArgumentException("piece " + p.piece().id() + " turned " + p.rotation()
                        + " does not fit at (" + r + "," + c + ")");
            grid[r][c] = p;
            used.add(p.piece().id());
            for (BoardListener l : listeners) l.placed(r, c, p, used.size());
        }

        synchronized void clear() {
            for (Placement[] row : grid) Arrays.fill(row, null);
            used.clear();
        }

        /** Every place() was checked, so a full board is a solved board. */
        synchronized boolean isComplete() { return used.size() == rows * cols; }

        /** Slow independent check used by the demo: every shared edge locks, every outer edge is flat. */
        synchronized boolean verify() {
            for (int r = 0; r < rows; r++)
                for (int c = 0; c < cols; c++) {
                    Placement p = grid[r][c];
                    if (p == null) return false;
                    if (c + 1 < cols && !p.edge(Side.RIGHT).fits(grid[r][c + 1].edge(Side.LEFT)))
                        return false;
                    if (r + 1 < rows && !p.edge(Side.BOTTOM).fits(grid[r + 1][c].edge(Side.TOP)))
                        return false;
                    if (r == 0 && p.edge(Side.TOP).type() != EdgeType.FLAT) return false;
                    if (c == 0 && p.edge(Side.LEFT).type() != EdgeType.FLAT) return false;
                }
            return true;
        }

        synchronized long fitChecks() { return fitChecks; }

        synchronized String render() {
            StringBuilder sb = new StringBuilder();
            for (Placement[] row : grid) {
                sb.append(" ");
                for (Placement p : row)
                    sb.append(p == null ? "   .  " : String.format("%4d/%d", p.piece().id(), p.rotation()));
                sb.append('\n');
            }
            return sb.toString();
        }
    }

    // ---------- finding a piece fast ----------
    record Slot(Piece piece, int edgeIndex) {}

    record Move(int row, int col, Placement placement) {}

    /** One step of a solving plan: a cell, and the side where a placed neighbour already is. */
    record Step(int row, int col, Side toward) {}

    /** Edge to the pieces that have it. Looking up the partner of a known edge is O(1). */
    static final class EdgeIndex {
        private final Map<Edge, List<Slot>> byEdge = new HashMap<>();
        private final List<Piece> corners = new ArrayList<>();

        EdgeIndex(List<Piece> pieces) {
            for (Piece p : pieces) {
                if (p.flats() == 2) corners.add(p);
                for (int i = 0; i < 4; i++) {
                    Edge e = p.edges().get(i);
                    if (e.type() != EdgeType.FLAT)
                        byEdge.computeIfAbsent(e, k -> new ArrayList<>()).add(new Slot(p, i));
                }
            }
        }

        List<Piece> corners() { return corners; }

        /** The unused piece and rotation that fits at (r, c), given the neighbour on side toward. */
        Optional<Placement> find(Board b, int r, int c, Side toward) {
            Placement known = b.at(r + toward.dr, c + toward.dc);
            if (known == null) return Optional.empty();
            Edge need = known.edge(toward.opposite()).partner();
            for (Slot s : byEdge.getOrDefault(need, List.of())) {
                if (b.isUsed(s.piece().id())) continue;
                // turn the piece so that edge s.edgeIndex() faces the known neighbour
                Placement p = new Placement(s.piece(), (toward.ordinal() - s.edgeIndex() + 4) % 4);
                if (b.canPlace(r, c, p)) return Optional.of(p);
            }
            return Optional.empty();
        }
    }

    // ---------- solvers: Strategy, with a shared corner loop (Template Method) ----------
    interface Solver { boolean solve(Board board, List<Piece> pieces); }

    abstract static class CornerFirstSolver implements Solver {
        /** Try each corner at the top-left; a wrong one fails fast and we clear and try the next. */
        @Override
        public final boolean solve(Board board, List<Piece> pieces) {
            EdgeIndex index = new EdgeIndex(pieces);
            if (index.corners().size() != 4) return false;
            for (Piece corner : index.corners()) {
                board.clear();
                for (int rot = 0; rot < 4; rot++) {
                    Placement p = new Placement(corner, rot);
                    if (board.canPlace(0, 0, p)) {
                        board.place(0, 0, p);
                        break;
                    }
                }
                if (board.at(0, 0) != null && fillRest(board, pieces, index)) return true;
            }
            board.clear();
            return false;
        }

        abstract boolean fillRest(Board board, List<Piece> pieces, EdgeIndex index);
    }

    /** Border ring first, then the inside row by row; every cell is one index lookup. */
    static final class IndexedSolver extends CornerFirstSolver {
        @Override
        boolean fillRest(Board b, List<Piece> pieces, EdgeIndex index) {
            int rows = b.rows, cols = b.cols;
            List<Step> plan = new ArrayList<>();
            // the border ring, clockwise from the corner: each cell knows the neighbour it came from
            for (int c = 1; c < cols; c++) plan.add(new Step(0, c, Side.LEFT));
            for (int r = 1; r < rows; r++) plan.add(new Step(r, cols - 1, Side.TOP));
            for (int c = cols - 2; c >= 0; c--) plan.add(new Step(rows - 1, c, Side.RIGHT));
            for (int r = rows - 2; r >= 1; r--) plan.add(new Step(r, 0, Side.BOTTOM));
            // then the inside, row by row: the left neighbour is always placed already
            for (int r = 1; r < rows - 1; r++)
                for (int c = 1; c < cols - 1; c++) plan.add(new Step(r, c, Side.LEFT));
            for (Step st : plan) {
                Optional<Placement> p = index.find(b, st.row(), st.col(), st.toward());
                if (p.isEmpty()) return false; // wrong corner choice: the caller tries the next one
                b.place(st.row(), st.col(), p.get());
            }
            return true;
        }
    }

    /** The naive way: for each cell, try every unused piece in all four rotations. */
    static final class BruteForceSolver extends CornerFirstSolver {
        @Override
        boolean fillRest(Board b, List<Piece> pieces, EdgeIndex index) { // ignores the index on purpose
            for (int r = 0; r < b.rows; r++)
                for (int c = 0; c < b.cols; c++) {
                    if (b.at(r, c) != null) continue;
                    boolean placed = false;
                    for (Piece p : pieces) {
                        for (int rot = 0; rot < 4 && !placed; rot++) {
                            Placement pl = new Placement(p, rot);
                            if (b.canPlace(r, c, pl)) {
                                b.place(r, c, pl);
                                placed = true;
                            }
                        }
                        if (placed) break;
                    }
                    if (!placed) return false;
                }
            return true;
        }
    }

    /** A hint for a human: the first empty cell next to a placed piece, and the piece that goes there. */
    static Optional<Move> hint(Board b, EdgeIndex index) {
        if (b.at(0, 0) == null) {
            for (Piece corner : index.corners())
                for (int rot = 0; rot < 4; rot++) {
                    Placement p = new Placement(corner, rot);
                    if (b.canPlace(0, 0, p)) return Optional.of(new Move(0, 0, p));
                }
        }
        for (int r = 0; r < b.rows; r++)
            for (int c = 0; c < b.cols; c++) {
                if (b.at(r, c) != null) continue;
                for (Side s : Side.values()) {
                    Optional<Placement> p = index.find(b, r, c, s);
                    if (p.isPresent()) return Optional.of(new Move(r, c, p.get()));
                }
            }
        return Optional.empty();
    }

    // ---------- making a puzzle ----------
    /** Cut a rows x cols picture: every inner edge gets a unique shape and a random tab side. */
    static List<Piece> cut(int rows, int cols, Random rnd) {
        Edge[][][] e = new Edge[rows][cols][4];
        int shape = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) {
                if (r == 0) e[r][c][Side.TOP.ordinal()] = Edge.FLAT;
                if (c == 0) e[r][c][Side.LEFT.ordinal()] = Edge.FLAT;
                if (r == rows - 1) e[r][c][Side.BOTTOM.ordinal()] = Edge.FLAT;
                if (c == cols - 1) e[r][c][Side.RIGHT.ordinal()] = Edge.FLAT;
                if (c + 1 < cols) {
                    Edge mine = new Edge(rnd.nextBoolean() ? EdgeType.TAB : EdgeType.BLANK, ++shape);
                    e[r][c][Side.RIGHT.ordinal()] = mine;
                    e[r][c + 1][Side.LEFT.ordinal()] = mine.partner();
                }
                if (r + 1 < rows) {
                    Edge mine = new Edge(rnd.nextBoolean() ? EdgeType.TAB : EdgeType.BLANK, ++shape);
                    e[r][c][Side.BOTTOM.ordinal()] = mine;
                    e[r + 1][c][Side.TOP.ordinal()] = mine.partner();
                }
            }
        List<Piece> out = new ArrayList<>();
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) out.add(new Piece(r * cols + c, List.of(e[r][c])));
        return out;
    }

    /** Tip the pieces into the box: random order, each turned a random number of quarter turns. */
    static List<Piece> scramble(List<Piece> pieces, Random rnd) {
        List<Piece> box = new ArrayList<>();
        for (Piece p : pieces) box.add(p.turned(rnd.nextInt(4)));
        Collections.shuffle(box, rnd);
        return box;
    }

    // ---------- demo ----------
    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        // 1. A small 4 x 5 puzzle, played by hand with hints.
        Random rnd = new Random(2026);
        List<Piece> box = scramble(cut(4, 5, rnd), rnd);
        int corners = 0, border = 0, inside = 0;
        for (Piece p : box) {
            if (p.flats() == 2) corners++;
            else if (p.flats() == 1) border++;
            else inside++;
        }
        System.out.println("4 x 5 box: " + corners + " corners, " + border + " border, "
                + inside + " inside");
        check(corners == 4 && border == 10 && inside == 6, "piece counts");

        Board small = new Board(4, 5);
        EdgeIndex index = new EdgeIndex(box);
        Piece middle = box.stream().filter(p -> p.flats() == 0).findFirst().orElseThrow();
        try {
            small.place(0, 0, new Placement(middle, 0));
            throw new AssertionError("an inside piece fitted a corner");
        } catch (IllegalArgumentException ex) {
            System.out.println("Rejected: " + ex.getMessage());
        }
        for (int i = 0; i < 3; i++) {
            Move m = hint(small, index).orElseThrow();
            if (i == 0) {
                Placement p = m.placement();
                Placement upsideDown = new Placement(p.piece(), (p.rotation() + 2) % 4);
                System.out.println("Corner turned upside down fits? " + small.canPlace(0, 0, upsideDown));
            }
            small.place(m.row(), m.col(), m.placement());
            System.out.println("Hint: piece " + m.placement().piece().id() + " turned "
                    + m.placement().rotation() + " at (" + m.row() + "," + m.col() + ")");
        }

        // 2. Solve it from scratch: border ring first, then row by row.
        check(new IndexedSolver().solve(small, box), "small puzzle should solve");
        System.out.print(small.render());
        System.out.println("Solved 4 x 5: complete " + small.isComplete() + ", verified " + small.verify());
        check(small.verify(), "every edge must lock");

        // 3. 1200 pieces: the edge index against trying every piece in every rotation.
        List<Piece> big = scramble(cut(30, 40, new Random(99)), new Random(100));
        Board fast = new Board(30, 40);
        int[] nextReport = {300};
        fast.subscribe((r, c, p, n) -> {
            if (n == nextReport[0]) {
                System.out.println("  placed " + n + " of 1200");
                nextReport[0] += 300;
            }
        });
        check(new IndexedSolver().solve(fast, big), "indexed solver failed");
        Board slow = new Board(30, 40);
        check(new BruteForceSolver().solve(slow, big), "brute force solver failed");
        System.out.println("30 x 40 indexed: " + fast.fitChecks() + " fit checks, verified " + fast.verify());
        System.out.println("30 x 40 brute force: " + slow.fitChecks() + " fit checks, verified "
                + slow.verify());
        check(fast.verify() && slow.verify(), "both boards must verify");
        check(fast.fitChecks() * 100 < slow.fitChecks(), "the index should be far cheaper");
    }
}

Notes

Requirements

Fix the scope first. The puzzle is a rectangle of R rows and C columns. Each piece has four edges, and each edge is flat, a tab that sticks out, or a blank that goes in. A tab locks only into a blank of the same shape. A player places a piece, turned any way, and the board rejects it if it does not fit. We detect a finished puzzle, and offer a solver and hints. Matching real photos is out of scope.

Ask the questions that change the code. Can a piece be flipped over? No, only turned in the plane, so four rotations. Are edge shapes unique? In our model each inner edge has its own shape number; with real photos shapes are only roughly unique, which is a follow-up. Can several people work on one board? Yes. And size matters: a few thousand pieces means trying every piece for every cell is too slow.

Requirements
  • a rectangle of R x C pieces
  • each piece has four edges:
  • flat, tab or blank
  • a tab locks into a blank of
  • the same shape
  • place a piece, turned any way
  • reject a piece that does not fit
  • know when the puzzle is done
  • a solver and hints
  • out of scope: real images
Clarify first
  • can pieces be flipped over?
  • no, only turned in the plane
  • are edge shapes unique?
  • in our model yes; in real
  • photos only roughly
  • loose pieces on the table?
  • only board cells matter
  • many players at once?
  • yes, one shared board
  • size?
  • up to a few thousand pieces

Entities

Underline the nouns: puzzle, piece, edge, side, board, cell. A piece has four edges. One design choice keeps everything clean: a piece never changes. Its rotation is not part of the piece but of where it is placed. So a placement is a piece plus a number of quarter turns, and the board holds a grid of placements. The same piece object can be tried in four rotations without copying it.

Class diagram

In code, an edge is a record of a type and a shape number. Its partner is the opposite type with the same shape, so tab seven pairs with blank seven. Two edges fit when one is the partner of the other, and a flat edge never fits anything. A piece is an id and four edges in a fixed clockwise order: top, right, bottom, left. Sides are an enum in that same clockwise order, which makes rotation simple arithmetic.

Value types
enum EdgeType { FLAT, TAB, BLANK }
enum Side { TOP, RIGHT, BOTTOM, LEFT }

record Edge(EdgeType type, int shape) {
  Edge partner()  // TAB 7 to BLANK 7
  boolean fits(Edge o) {
    return type != FLAT
        && partner().equals(o); }
}
record Piece(int id, List<Edge> edges)
record Placement(Piece piece, int rot)

Rotation

Turning a piece clockwise once moves the top edge to the right side, the right edge to the bottom, and so on. So to ask which edge now faces a side, subtract the rotation from the side number, modulo four. With one turn, the edge now facing left is edge number two, the old bottom. No arrays are rebuilt, so trying all four rotations is free.

Placement.edge(side)
Edge edge(Side s) {
  return piece.edges()
    .get((s.ordinal() - rot + 4) % 4);
}

one clockwise turn: what was on
  TOP now faces RIGHT
rot 1, side LEFT (3): edge 2,
  the old BOTTOM
four rotations, zero copies

Fit check

The board checks a fit by looking at all four sides. If the side faces outside the board, the edge must be flat, because the border is straight. If it faces another cell, the edge must not be flat, because a flat edge never points inwards. And if that neighbour is already placed, my edge must lock with its opposite edge. Place calls this check and throws if it fails, so the board can never hold a wrong fit.

Try the top-left cell. It needs flat edges on top and on the left, and real edges on the right and bottom. A corner piece turned the right way passes. The same corner turned upside down has its flat edges facing right and down, so it is rejected. An inside piece has no flat edges at all and fails on the very first side. The demo prints both rejections.

Board.canPlace(r, c, p)
cell free and piece unused?
for each side s:
  mine = p.edge(s)
  outside the board:
    mine must be FLAT
  neighbour cell, empty:
    mine must not be FLAT
  neighbour placed:
    mine.fits(their edge(s.opposite()))
Corner at (0,0)
  • needs: TOP flat, LEFT flat
  • RIGHT and BOTTOM not flat
  • corner turned the right way: ok
  • same corner turned twice:
  • flats face RIGHT and BOTTOM
  • rejected
  • an inside piece: no flats
  • rejected on TOP

The naive search

The first idea is to fill each cell by trying every unused piece in all four rotations. That is what a person at a table does. For N pieces it costs roughly two times N squared fit checks. For twelve hundred pieces the demo counts almost three million checks. It works for a small puzzle, but the work grows with the square of the size, and the interviewer will ask you to do better.

Brute force
for each cell:
  for each unused piece:
    for rot in 0..3:
      if canPlace: place, next cell

N pieces: about 2 x N x N checks
1200 pieces: 2,880,486 checks

a person does the same thing:
  pick up pieces until one fits

Edge index

Here is the key idea. When we fill a cell, we already know at least one neighbour, so we know the exact edge we need: the partner of the neighbour's facing edge. So build a hash map once, from every edge to the pieces that have it and at which position. Finding the next piece becomes one lookup. With unique shapes, the list holds exactly one piece, so every cell costs constant time instead of a scan.

Walk one lookup. The left neighbour shows tab forty one on its right side, so we need blank forty one. The index says piece twelve has it as edge number one. That edge must face left, which is side three, so the rotation is three minus one, which is two quarter turns. One full fit check confirms the other sides, and we place it. No guessing at rotations at all.

EdgeIndex
record Slot(Piece piece, int edgeIndex)
Map<Edge, List<Slot>> byEdge

build: for each piece, each edge i
  if not FLAT: byEdge[edge] += (p, i)

find(cell, toward known neighbour):
  need = known.edge(opposite).partner()
  for (Slot s : byEdge.get(need))
    rot = (toward - s.edgeIndex) mod 4
    if canPlace: return it
Walk one lookup
  • left neighbour shows TAB 41
  • on its RIGHT side
  • need: BLANK 41
  • index: piece 12 has it as edge 1
  • it must face LEFT (side 3)
  • rot = (3 - 1 + 4) % 4 = 2
  • canPlace confirms the other
  • sides, then place

Strategy: solvers

Solvers are a Strategy, so the demo can run both and compare them. They share one outer loop, written once in an abstract base class, which is the Template Method pattern. Pick a corner piece, turn it so its flat edges face top and left, place it, and let the subclass fill the rest. On a non-square puzzle a wrong corner makes the board the wrong shape, so filling fails quickly and we try the next corner.

Solver
interface Solver {
  boolean solve(Board b, List<Piece> p);
}
abstract class CornerFirstSolver:
  for each of the 4 corners:
    clear, place it at (0,0)
    if (fillRest(...)) return true
IndexedSolver: index lookups
BruteForceSolver: try everything

Flow: border first

The solver builds the border first, the way people do. From the corner it walks the ring clockwise: along the top row, down the right column, back along the bottom row and up the left column. Each cell knows the neighbour it came from, so each one is a single index lookup. The fit check makes sure flat edges face outward, and the last cell of the ring is checked against both of its neighbours.

The border ring
top row:      (0, 1..C-1), from LEFT
right column: (1..R-1, C-1), from TOP
bottom row:   (R-1, C-2..0), from RIGHT
left column:  (R-2..1, 0), from BOTTOM

each step: index.find(cell, side)
canPlace also checks flats face out
last cell checks both its neighbours

Flow: fill the inside

Then fill the inside row by row. For every inside cell the left neighbour is already placed, so we look up the partner of its right edge, and the fit check also confirms the top neighbour. On twelve hundred pieces the indexed solver needs about two thousand four hundred fit checks, against almost three million for brute force. That is linear work instead of quadratic.

Inside, row by row
for r in 1..R-2:
  for c in 1..C-2:
    find(r, c, LEFT)
    canPlace also checks TOP

1200 pieces: 2,403 fit checks
  against 2,880,486 brute force
O(N) instead of O(N squared)

Completion

How do we know the puzzle is finished? Because place refuses any piece that does not fit, the board can only ever hold correct fits. So a full board is a solved board, and completion is just a count of placed pieces compared with rows times columns. That is constant time. The tests also run a slow verify that rechecks every shared edge, as an independent check of the fast path.

Done?
boolean isComplete() {
  return used.size() == rows * cols;
}

place() never accepts a bad fit,
  so a count is enough: O(1)
verify(): slow full scan,
  used only by tests

Hints

A hint reuses the same parts. If the board is empty, suggest a corner for the top-left cell. Otherwise find the first empty cell that touches a placed piece, look up the partner of that neighbour's edge in the index, and return the piece, the rotation and the cell. The player still has to place it, and the board still checks the fit, so a hint can never break the rules.

Observer

The board never prints. After each placement it notifies listeners with the cell, the placement and the count so far. A progress bar, a celebration screen when the count is full, and the screens of other players in a shared game all subscribe the same way. Listeners live in a copy-on-write list, so a new player can join while others are placing pieces.

Concurrency

With many players on one board, two people can drop a piece on the same cell at the same moment. Place is synchronized, so the fit check and the write happen together; the second drop sees the cell taken and is rejected. The used set stops the same piece being placed twice. For very large shared boards, you can lock per region or run each board as an actor with a queue of moves.

Multiplayer
  • place() is synchronized:
  • fit check + write together
  • second drop on the same cell:
  • cell taken, rejected
  • same piece dragged twice:
  • used set rejects it
  • huge boards: lock per region
  • or one actor per board

Extensibility

Interviewers will push toward real images. Real pieces are scanned, so an edge holds a curve signature, not a clean number. Index by a coarse hash of that signature, then score the few candidates by shape and by the colours along the edge, and pick the best. Because two shapes can look alike, the solver may need backtracking. Timers and scores are listeners, and a saved game is just its list of placements.

Extension points
  • real photos: Edge holds a curve
  • signature; index by a coarse
  • hash, score the few candidates
  • similar shapes: backtracking
  • in fillRest
  • image matching: colour along
  • each edge joins the score
  • timer and scores: listeners
  • save game: list of placements

Testing

The full code is below the player. A cutter gives every inner edge a unique shape and a random tab side, and a scrambler shuffles the pieces and turns each one, both with a seeded random generator, so every run is identical. The demo rejects bad placements, takes three hints, solves a small puzzle, then solves a twelve hundred piece puzzle both ways and verifies both boards.

Run it
4 x 5 box: 4 corners, 10 border, 6 inside
Rejected: piece 12 turned 0 does not fit
Corner turned upside down fits? false
Hint: piece 15 turned 0 at (0,0)
Solved 4 x 5: complete true, verified true
placed 300 of 1200 ... 1200 of 1200
30 x 40 indexed: 2403 fit checks
30 x 40 brute force: 2880486 fit checks
  both verified

Follow-ups

Expect follow-ups. Why is rotation not stored on the piece? So pieces stay immutable and can be tried in any turn. How do you find a piece fast? A map from each edge to the pieces that carry it. Why start with the border? Flat edges cut the choices sharply. And a square puzzle can come out turned as a whole; picking the corner by its picture fixes that.

Follow-ups to expect
  • why is rotation not on Piece?
  • pieces stay immutable
  • how to find a piece fast?
  • map from edge to pieces
  • why start with the border?
  • flats narrow the choices
  • solved image upside down?
  • pick the corner by picture
  • pieces flipped over?
  • eight orientations, mirror

Say it like this

Here is the short version to say out loud. A piece has four edges: flat, or a tab or blank with a shape number. A placement adds the rotation, so pieces never change. The board checks all four sides on every place. An index from each edge to the pieces that carry it finds the next piece in constant time, border ring first and then row by row. And since every place was checked, a full board means solved.

In the interview
  • "A piece is four edges: flat,
  • tab or blank with a shape. A
  • placement adds the rotation.
  • The board checks all four sides
  • on place. An index from edge to
  • pieces finds each next piece in
  • O(1): border ring first, then
  • row by row. A full board
  • means solved."

Interview questions

How do you model a jigsaw piece?

A piece is an id plus four edges in clockwise order. Each edge is FLAT, TAB or BLANK with a shape number; a TAB fits only a BLANK of the same shape. The piece is immutable, and its rotation is stored on the Placement, not on the piece.

How do you handle rotation without copying edges?

Keep sides in clockwise order and store a rotation from 0 to 3 on the placement. The edge facing side s is edges[(s - rotation + 4) % 4], so all four rotations are simple index arithmetic.

How does the board check that a piece fits?

For each of the four sides: if it faces outside the board the edge must be flat; if it faces a cell the edge must not be flat; and if that cell is filled, the edge must lock with the neighbour's opposite edge. place() runs this check and rejects any failure.

How do you find the matching piece faster than trying all of them?

Build a map from each non-flat edge to the pieces (and edge positions) that carry it. To fill a cell, take the known neighbour's facing edge, look up its partner, and compute the rotation that turns that edge toward the neighbour. This is O(1) per cell instead of O(N).

Why solve the border first?

Border pieces are easy to recognise by their flat edges, and the ring gives every inside cell a known left and top neighbour. After the ring, the inside can be filled row by row with one lookup per cell.

How do you detect that the puzzle is complete?

Because place() never accepts a bad fit, the board only ever contains correct fits. So the puzzle is solved exactly when the number of placed pieces equals rows times columns, an O(1) check.

What changes when edges come from real photos?

Shapes are no longer exact ids, so an edge holds a curve signature. Index by a coarse hash of it, score the few candidates by shape and colour along the edge, and keep backtracking in the solver in case two candidates look alike.

How do you make a shared board safe for many players?

Make the fit check and the write one synchronized step, so two drops on the same cell cannot both win. A set of used piece ids stops one piece being placed twice. For very large boards, lock per region or process moves on one actor thread per board.

Why is the solver a Strategy, and where is Template Method used?

Different solvers (brute force, indexed, image scoring) are swappable behind a Solver interface, which also lets tests compare them. The shared corner loop lives once in an abstract base class, and each subclass supplies only the fillRest step.