Design the classes and a solve method for a rectangular jigsaw puzzle when the grid dimensions are unknown. You are given all the piece objects. Each piece exposes four sides in a fixed cyclic order, such as north, east, south, and west. A side is either flat, an outward tab, or an inward blank. A provided predicate match(sideA, sideB) reports whether two non-flat sides fit together. Pieces may be rotated by any multiple of 90 degrees.
The solver must return a two-dimensional array of oriented piece objects. The completed rectangle must satisfy three placement rules: every side on the outer perimeter is flat, every pair of touching non-flat sides passes match, and each physical piece is used exactly once. The same piece object may not appear more than once in the grid, even in a different rotation.
match is symmetric and returns false whenever either argument is flat. For every non-flat side, the input contains exactly one matching side. The input is guaranteed to describe one valid rectangular puzzle; if the same physical rectangle can be interpreted with the row and column counts exchanged, either output is acceptable.
Although normal inputs are valid, specify how solve reports an impossible or ambiguous instance. Explain your representation for pieces and rotations, how dimensions are derived, how candidates are indexed, how backtracking and rollback are handled, and the time and space complexity. Pseudocode or a real programming language is accepted.
Examples below use symbolic edge IDs for readability; an actual implementation can use any edge object or descriptor accepted by match.
Example 1:
Input:
pieces = [A, B, C, D, E, F]
Edge order: [North, East, South, West]
A: [FLAT, e1, e5, FLAT]
B: [FLAT, e2, e6, e1c]
C: [FLAT, FLAT, e7, e2c]
D: [e5c, e3, FLAT, FLAT]
E: [e6c, e4, FLAT, e3c]
F: [e7c, FLAT, FLAT, e4c]
match pairs: e1-e1c, e2-e2c, e3-e3c, e4-e4c, e5-e5c, e6-e6c, e7-e7c
Output:
[[A, B, C], [D, E, F]]
Explanation: The top row has flat north sides, the bottom row has flat south sides, the left and right borders are flat, and all internal touching sides are matching pairs.
Example 2:
Input:
pieces = [K]
K: [FLAT, FLAT, FLAT, FLAT]
Output:
[[K]]
Explanation: A single piece with all four sides flat forms a 1 by 1 rectangle.
Example 3:
Input:
pieces = [L, R]
L: [FLAT, e1, FLAT, FLAT]
R: [FLAT, FLAT, FLAT, e1c]
match pairs: e1-e1c
Output:
[[L, R]]
Explanation: The only matching non-flat sides are L's east side and R's west side, so they must touch.
Constraints:
match is symmetric and returns false if either side is flat.