Katkat
Back

Solve a Jigsaw Puzzle

AsanaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates algorithmic problem-solving, constraint satisfaction, search and pruning strategies, and handling combinatorial state such as piece rotation and placement.

You are given a collection of jigsaw puzzle pieces. Each piece has four edges — top, right, bottom, and left — and a helper function match(edgeA, edgeB) is provided that returns true if two edges can be physically connected and false otherwise.

The pieces are known to form exactly one complete rectangular grid, but the number of rows $R$ and columns $C$ is not given (only that $R \times C = N$, the total number of pieces). Pieces may need to be rotated by $0°$, $90°$, $180°$, or $270°$ to fit.

Implement a function solve(pieces) that returns a valid rectangular arrangement of all pieces — including each piece's chosen orientation — such that every pair of horizontally- or vertically-adjacent edges matches according to match.

You may assume:

  • Every piece must be used exactly once.
  • A valid solution is guaranteed to exist.
  • The puzzle has no missing pieces.
  • Border edges (those on the outer boundary of the grid) do not need to match anything outside the puzzle.

Walk through your algorithm, the data structures you use, how you handle rotation and the unknown grid dimensions, and the time and space complexity.

Constraints & Assumptions

  • $N = R \times C$ pieces total; $R$ and $C$ are unknown but $R \times C = N$ exactly, with $R, C \ge 1$.
  • Each piece is a 4-tuple of edges; edges are opaque values compared only through match (do not assume ==, hashing, or an ordering on edges unless you ask).
  • match is the only oracle for compatibility — assume it is reasonably cheap (treat as $O(1)$) and symmetric, i.e. match(a, b) == match(b, a). Still, count match calls, since interviewers often probe how many you make.
  • You are not told whether matching is one-to-one. An edge could be compatible with exactly one other edge or with several; your approach must be correct either way, and you should state how this selectivity affects performance.
  • Rotating a piece cyclically permutes its edges: a $90°$ clockwise rotation maps [top, right, bottom, left] → [left, top, right, bottom].
  • Pieces are distinguishable objects; "use each exactly once" is by identity, not by edge values.
  • A solution is guaranteed, so you do not need to report "no solution" — but your code should still terminate cleanly if pruning exhausts a candidate grid shape.

Clarifying Questions to Ask

  • Is the solution unique, or may there be multiple valid arrangements — and do we need all of them or just one?
  • Can a single edge be compatible with many other edges, or is match close to a perfect bijection on the true neighbors?
  • How are pieces and edges represented? Can I compare/hash edges directly, or only through match?
  • For border edges, is there a sentinel/null edge I can detect, or do I infer "this is a border" purely from the grid position I'm filling?
  • What is the expected scale of $N$ — dozens, thousands, or millions? Does that change the acceptable complexity?
  • Should the returned arrangement include each piece's absolute position and rotation, or just relative adjacency?

Hints

Hint 1

Where to start: Two unknowns make this hard: the grid shape and each piece's rotation. Pin down the grid shape first — $N$ has only a handful of factor pairs $(R, C)$, so you can try each one. Within a fixed grid, place pieces cell-by-cell in reading order (row-major), so each new piece only has to satisfy its **already-placed** left and top neighbors.

Hint 2

Reduce the search with edge buckets: A naive search tries every remaining piece in every rotation at every cell. Prune it: bucket pieces/edges so that, given the required `right` edge of the left neighbor and the required `bottom` edge of the top neighbor, you can look up only the candidates whose corresponding edge could `match`, instead of scanning all $N$ pieces. Corner and border pieces (those with one or two "outside" edges that need no match) are a natural place to anchor the search.

Hint 3

It's backtracking — make it correct first, fast second: This is constraint-satisfaction / backtracking: place a candidate, recurse, and **undo** (restore the piece to the available pool) if the recursion dead-ends. A correct backtracker that exploits the "a solution exists" guarantee and prunes hard usually finishes quickly; don't reach for anything fancier until you've nailed the place/recurse/undo skeleton and the rotation bookkeeping.

Follow-up questions

  • If `match` is **expensive** (e.g. a network or vision call), how do you minimize the number of calls? What can you cache or precompute?
  • How would you parallelize or distribute the search across many cores or machines, and where are the synchronization points?
  • How does the approach change if the puzzle is **not** guaranteed solvable and you must detect "no solution," or if some pieces are missing and the boundary is irregular?
  • How would you adapt this if pieces could also be **flipped** (mirrored), not just rotated, or if `match` can return false positives/negatives?