# Model and Solve a Rectangular Jigsaw Puzzle Design an object-oriented model for a rectangular jigsaw puzzle and outline an algorithm to solve it. Use concepts such as `Puzzle`, `Piece`, and `Edge`. Each piece has four edges that are flat, inward, or outward and may be rotated. Flat edges belong on the outer border; inward and outward edges may fit when their shapes are compatible. Assume the puzzle dimensions and all pieces are supplied. Return one valid two-dimensional arrangement of oriented pieces, using each piece once. Explain how you identify corner and border candidates, what data structures support matching, and how the solver recovers from a placement that later proves wrong. ### Constraints & Assumptions - The puzzle is rectangular and has at least one valid solution. - A compatibility function decides whether two concrete edges match. - Rotating a piece changes edge positions but not piece identity. - Returning any valid arrangement is sufficient. ### Clarifying Questions to Ask - Can one edge match multiple candidates, or is every match unique? - Are mirror reflections forbidden? - Do edge shapes have stable keys suitable for hashing? - Should the API report all solutions or only the first? ### What a Strong Answer Covers - Cohesive classes with immutable piece identity and explicit orientation - Boundary, corner, and adjacency constraints - Search ordering, candidate indexes, and exact rollback - A final validity check and behavior for malformed input - Honest worst-case complexity and practical pruning ### Follow-up Questions - Which cell should the search fill first? - How would duplicate-looking pieces affect the design? - Can matching be precomputed? - How would you make the solver cancellable?