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. ```hint 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 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 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. ``` ### 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? ### What a Strong Answer Covers - **Decomposition of the two unknowns**: a clear plan to resolve grid dimensions (enumerate factor pairs of $N$) separately from per-piece rotation. - A clean **model of a piece and its orientation** so reading any rotated edge is cheap, rather than physically reshuffling data per rotation. - **Cell-by-cell placement in reading order** so each placement is constrained only by already-placed left/top neighbors — turning a global problem into a sequence of local checks. - **Pruning strategy**: edge buckets / candidate lookup, anchoring on corner/border pieces, and early termination of impossible factor pairs or partial grids. - **Backtracking correctness**: marking a piece used, recursing, and properly restoring state on failure (no piece leaks, no double-use). - A correct **complexity analysis** that separates the typical/well-formed case from the adversarial worst case, plus the space used by the visited/used structures. - **Edge cases**: $1 \times N$ and $N \times 1$ strips, $N = 1$, duplicate/ambiguous edge values, symmetric pieces, and how to verify the final grid. ### 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?