Cracking The Coding Interview Together – Problem 7.6: Jigsaw Puzzle

When you and I solve a physical jigsaw puzzle, our human brain performs astounding parallel computation. We instantly scan a pile of cardboard pieces, pick out the ones with flat edges to form the border, group similar color palettes, and visually match interlocking tabs and sockets. But how do we translate this intuitive spatial problem into a computer program?

Without visual intuition, a computer must rely entirely on abstract data structures and strict algorithmic logic. How do we model the physical characteristics of a puzzle piece—its edges, orientation, and shape—in clean Object-Oriented Design (OOD)? More importantly, how do we craft a solver algorithm that doesn't explode into an uncomputable brute-force combination space?

In this post, we are going to model an $N \times N$ jigsaw puzzle from the ground up. We will design expressive, production-ready data structures in Java and walk through a structured algorithm that solves the puzzle systematically while minimizing computational overhead.

Problem Statement

Design the data structures and algorithm for an $N \times N$ jigsaw puzzle. You may assume that you have a method fitsWith(Edge edge1, Edge edge2) that tells you whether two edges can interlock successfully.

Operational Goals:

• Define data models for puzzle pieces, edge geometries, piece orientations, and the assembly board.
• Implement rotation and orientation mechanics so pieces can be positioned flexibly in 2D space.
• Design an algorithmic solver that takes $N^2$ unplaced, unoriented pieces and correctly reconstructs the $N \times N$ board layout.

Analyze the Problem Together

Let's step back and analyze what makes a jigsaw piece unique. A puzzle piece has four sides: Top, Right, Bottom, and Left. Each side has an Edge. Physically, an edge can take three forms:

• FLAT: A straight outer boundary edge.
• OUTER (Tab): A protruding shape that fits into an indentation.
• INNER (Socket): An indentation shape designed to receive a tab.

The core conflict in this design lies in matching efficiency versus search space explosion. If we treat every piece as a generic blob and attempt to place pieces onto the board blindly, we face a permutation nightmare. For an N * N puzzle, there are N^2 pieces. Each piece can be rotated in 4 orientations.

A naive brute-force approach would attempt (N^2)! * 4^{N^2} configurations. For even a tiny 10 * 10 puzzle (100 pieces), (100)! * 4^{100} is vastly larger than the number of atoms in the observable universe. Clearly, brute-force is non-viable.

To prune this search space dramatically, we can categorize our pieces prior to assembly based on their edge signatures:

By categorizing pieces into these distinct buckets during preprocessing, we constrain our search space at every step. When building the top-left corner, we only check the 4 corner pieces. When assembling border cells, we only check remaining border pieces. When filling internal cells, we only look at inner pieces.

Questions for the Interviewer

Before writing a single line of code, a senior engineer asks targeted clarifying questions to establish boundaries and assumptions:

1. Does fitsWith guarantee absolute uniqueness? Can an edge fit multiple other edges conceptually, requiring backtracking, or is a geometric/pattern match 100% unique across the set? (Assumption: We will design for the realistic case where multiple pieces might geometrically fit, using a backtracking solver, but optimization will keep branches short).
2. Can pieces be flipped face-down (3D reflection)? Or are they restricted to 2D rotational turns (0, 90, 180, 270 degrees)? (Assumption: Only 2D planar rotations are allowed).
3. Is the puzzle guaranteed to be complete and solvable? Are there duplicate or missing pieces in the input set? (Assumption: The input contains exactly $N^2$ valid pieces forming a solvable $N \times N$ square).

Think About the Solution

Let's map out our domain entities cleanly before writing code:

• EdgeType: An enum representing FLAT, OUTER, and INNER.
• Orientation: An enum representing NORTH, EAST, SOUTH, WEST with helper methods to rotate clockwise.
• Edge: Stores its EdgeType and a reference to its parent Piece. It exposes a fitsWith(Edge other) method. Flat edges never fit any edge. An OUTER edge only fits an INNER edge (and vice-versa).
• Piece: Holds an array of 4 Edge objects in absolute index order (0: North, 1: East, 2: South, 3: West). Rotating a piece simply shifts our index offset or shifts the edge references.
• Puzzle: Manages the $N \times N$ board (a 2D array of pieces), categorizes input pieces into corners, borderEdges, and insidePieces, and executes the solver algorithm.

The Solving Algorithm Step-by-Step:

1. Partition the $N^2$ unplaced pieces into three pools: corners, borders, and inners.
2. Select a corner piece, rotate it so its two flat edges face North and West, and place it at position (0,0).
3. Iterate through the grid row-by-row, column-by-column from top-left to bottom-right:
   • Identify the target pool (Corner for 4 corners, Border for outer edges, Inner for internal cells).
   • Find a piece from the pool that fits with the Left neighbor's East edge AND the Top neighbor's South edge (if applicable).
   • Rotate the piece until all adjacent edges match. Place it on the board and recurse/continue.

Write Code and Explain

Here is the robust, object-oriented Java implementation for our $N \times N$ Jigsaw Puzzle solver:

package com.thedevlearnings.jigsaw;

import java.util.*;

enum EdgeType {
    FLAT, OUTER, INNER;

    public boolean isOpposite(EdgeType other) {
        if (this == FLAT || other == FLAT) return false;
        return this != other; // OUTER matches INNER, INNER matches OUTER
    }
}

enum Orientation {
    NORTH(0), EAST(1), SOUTH(2), WEST(3);

    private final int value;
    Orientation(int value) { this.value = value; }
    public int getValue() { return value; }

    public Orientation rotateClockwise() {
        return values()[(this.value + 1) % 4];
    }
}

class Edge {
    private final EdgeType type;
    private final int id; // Unique identifier for edge matching validation
    private Piece parentPiece;

    public Edge(EdgeType type, int id) {
        this.type = type;
        this.id = id;
    }

    public EdgeType getType() { return type; }
    public void setParentPiece(Piece piece) { this.parentPiece = piece; }
    public Piece getParentPiece() { return parentPiece; }

    /**
     * Returns true if this edge physically and visually matches another edge.
     */
    public boolean fitsWith(Edge other) {
        if (other == null) return false;
        if (!this.type.isOpposite(other.getType())) return false;
        // In a real system, image matching or unique edge IDs confirm a match
        return this.id == -other.id;
    }
}

class Piece {
    private final Edge[] edges = new Edge[4]; // 0: North, 1: East, 2: South, 3: West
    private Orientation currentOrientation = Orientation.NORTH;

    public Piece(Edge north, Edge east, Edge south, Edge west) {
        edges[0] = north; edges[1] = east; edges[2] = south; edges[3] = west;
        for (Edge e : edges) {
            if (e != null) e.setParentPiece(this);
        }
    }

    public void rotateClockwise() {
        Edge last = edges[3];
        edges[3] = edges[2];
        edges[2] = edges[1];
        edges[1] = edges[0];
        edges[0] = last;
        currentOrientation = currentOrientation.rotateClockwise();
    }

    public Edge getEdge(Orientation orientation) {
        return edges[orientation.getValue()];
    }

    public int countFlatEdges() {
        int count = 0;
        for (Edge e : edges) {
            if (e.getType() == EdgeType.FLAT) count++;
        }
        return count;
    }

    public boolean isCorner() { return countFlatEdges() == 2; }
    public boolean isBorder() { return countFlatEdges() == 1; }
    public boolean isInner() { return countFlatEdges() == 0; }
    public Orientation getCurrentOrientation() { return currentOrientation; }
}

public class Puzzle {
    private final int size; // N
    private final Piece[][] board;
    private final List<Piece> corners = new ArrayList<>();
    private final List<Piece> borderEdges = new ArrayList<>();
    private final List<Piece> insidePieces = new ArrayList<>();

    public Puzzle(int size, List<Piece> pieces) {
        this.size = size;
        this.board = new Piece[size][size];
        categorizePieces(pieces);
    }

    private void categorizePieces(List<Piece> pieces) {
        for (Piece p : pieces) {
            if (p.isCorner()) corners.add(p);
            else if (p.isBorder()) borderEdges.add(p);
            else insidePieces.add(p);
        }
    }

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

    private boolean solveCell(int row, int col) {
        if (row == size) return true; // Entire board filled successfully

        int nextRow = (col == size - 1) ? row + 1 : row;
        int nextCol = (col == size - 1) ? 0 : col + 1;

        List<Piece> pool = getPoolForCell(row, col);

        for (int i = 0; i < pool.size(); i++) {
            Piece piece = pool.get(i);

            for (int rotation = 0; rotation < 4; rotation++) {
                if (isValidPlacement(piece, row, col)) {
                    board[row][col] = piece;
                    pool.remove(i);

                    if (solveCell(nextRow, nextCol)) return true;

                    // Backtrack
                    pool.add(i, piece);
                    board[row][col] = null;
                }
                piece.rotateClockwise();
            }
        }
        return false;
    }

    private List<Piece> getPoolForCell(int row, int col) {
        boolean isRowBorder = (row == 0 || row == size - 1);
        boolean isColBorder = (col == 0 || col == size - 1);

        if (isRowBorder && isColBorder) return corners;
        if (isRowBorder || isColBorder) return borderEdges;
        return insidePieces;
    }

    private boolean isValidPlacement(Piece piece, int row, int col) {
        // Validate Flat edges against outer boundary limits
        if (row == 0 && piece.getEdge(Orientation.NORTH).getType() != EdgeType.FLAT) return false;
        if (row == size - 1 && piece.getEdge(Orientation.SOUTH).getType() != EdgeType.FLAT) return false;
        if (col == 0 && piece.getEdge(Orientation.WEST).getType() != EdgeType.FLAT) return false;
        if (col == size - 1 && piece.getEdge(Orientation.EAST).getType() != EdgeType.FLAT) return false;

        // Validate match with Top neighbor
        if (row > 0) {
            Piece topNeighbor = board[row - 1][col];
            if (!piece.getEdge(Orientation.NORTH).fitsWith(topNeighbor.getEdge(Orientation.SOUTH))) {
                return false;
            }
        }

        // Validate match with Left neighbor
        if (col > 0) {
            Piece leftNeighbor = board[row][col - 1];
            if (!piece.getEdge(Orientation.WEST).fitsWith(leftNeighbor.getEdge(Orientation.EAST))) {
                return false;
            }
        }

        return true;
    }
    
    public Piece[][] getBoard() { return board; }
}

Code Walkthrough

• Categorization Phase: Before solving, categorizePieces() filters input pieces into corners, borderEdges, and insidePieces. This isolates piece sets completely.
• Rotation Logic: The rotateClockwise() method in Piece shifts the Edge array indices in $O(1)$ time and tracks relative orientation.
• Placement Validation: isValidPlacement() checks boundary alignment (e.g., ensuring a top boundary cell gets a FLAT top edge) and verifies that the candidate piece's top and left edges interlock seamlessly with the already placed neighbors at board[row-1][col] and board[row][col-1].
• Backtracking Core: solveCell() places candidate pieces from the appropriate pool. If a path leads to a dead end, it backtracks gracefully by restoring the candidate piece to the pool and clearing the matrix cell.

Time & Space Complexity

Space Complexity: $O(N^2)$

• The board matrix holds $N \times N$ references ($O(N^2)$ space).
• The piece pools (corners, borders, inners) collectively store $N^2$ elements ($O(N^2)$ space).
• The call stack recursion depth for solveCell reaches at most $N^2$ frames, contributing $O(N^2)$ auxiliary space.

Time Complexity:

• Preprocessing (Categorization): Inspecting 4 edges for $N^2$ pieces takes $O(N^2)$ time.
• Solving Phase:
  • Best/Average Case (Unique Edge Fits): If edge signatures are unique (or nearly unique), finding the matching piece for each cell takes $O(1)$ lookup time within its small pool. Placing $N^2$ pieces takes $O(N^2)$ total time.
  • Worst Case (Ambiguous/Identical Edges): If many edges share identical shapes, backtracking searches across pool choices. However, because we partition into pools and enforce 2-neighbor constraints (Top + Left) at every step beyond the first row/col, the branching factor $K$ is drastically reduced compared to raw permutation search, executing in $O(N^2 \cdot K)$ time.

Why This Problem Matters (The Senior Perspective)

This problem is rarely about building an actual jigsaw game in a real tech interview. Instead, it serves as an architectural test of how you handle **spatial domain modeling**, **state representation**, and **pruning search spaces**.

Consider real-world applications of this exact design pattern:

• Genomics & DNA Sequencing: Shotgun sequencing breaks DNA into millions of short reads. Reconstructing the full genome requires matching overlapping sequence boundaries—conceptually identical to fitting jigsaw pieces together.
• Computer Vision & Dynamic Stitching: Creating 360-degree panoramic photos or aerial satellite maps requires matching overlapping image features across adjacent tiles.
• 2D Tile Engine Game Architecture: Procedural world generation (such as Wave Function Collapse algorithms in game design) relies on strict boundary edge rules between adjacent terrain tiles.

By enforcing clean separation of concerns (separating physical geometry in Edge, spatial orientation in Piece, and grid constraints in Puzzle), your architecture remains maintainable, extensible, and performant.

Final Thoughts

By breaking down a complex physical problem into clear geometric abstractions and leveraging preprocessing bucket classification, we transformed an impossible $(N^2)!$ search space into a clean, deterministic grid traversal algorithm.

As a next step, consider how you would adapt this system if piece edges weren't purely discrete enums, but raw 2D point clouds extracted from camera images. How would you adjust fitsWith to account for mathematical tolerance and noise?

Happy coding, and we'll see you in the next deep dive on The Dev Learnings!