# Design and Solve a Rotatable Jigsaw Puzzle Design the classes and a `solve` operation for a rectangular jigsaw puzzle. You are given all pieces, but not the number of rows or columns. Each piece has four edges. An edge is flat, inward, or outward; a supplied `match(edge_a, edge_b)` function tells whether two non-flat edges fit. Every non-flat edge has exactly one matching edge among all pieces. Pieces may be rotated in 90-degree increments. `solve` must return a two-dimensional array of oriented pieces. Flat edges must lie on the outside boundary, all adjacent interior edges must match, and every piece must be used exactly once. Pseudocode or a real programming language is acceptable. ### Constraints & Assumptions - The input describes one valid rectangular puzzle, up to swapping rows and columns. - A physical piece may appear at most once in the result, regardless of orientation. - `match` is symmetric and returns false for flat edges. - Explain how an impossible or ambiguous input would be reported even though the primary input is valid. ### Clarifying Questions to Ask - Does a square puzzle need one canonical orientation, or is any valid rotation acceptable? - Are edge IDs or shapes available for indexing, or can compatibility only be discovered by calling `match`? - Can a piece have more than two flat sides? - Is returning the first valid arrangement sufficient? ### What a Strong Answer Covers - A representation for pieces, edges, orientation, and placement without copying identity - Derivation and validation of the unknown dimensions - Boundary and neighbor constraints applied before expensive search - Candidate indexing and backtracking with correct rollback - Complexity, malformed inputs, and tests for rotations and corners ### Follow-up Questions - How would the solver change if an edge could match several others? - Can you detect the dimensions before attempting placement? - How would you avoid recomputing rotated edges? - What test would expose accidentally reusing one piece in two orientations?