Katkat
Back

Model and Solve a Rectangular Jigsaw Puzzle

AsanaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests object-oriented modeling skills and the ability to implement a backtracking algorithm with state pruning for a combinatorial search task.

Problem Statement

You are tasked with building a system to solve a rectangular N x M jigsaw puzzle. Each piece has four sides, and each side has a specific 'shape' ID. Two pieces are compatible at their touching edges if their shape IDs are matching (e.g., side A of piece 1 must 'fit' side B of piece 2).

Define a Piece class that supports rotation and a PuzzleSolver class that identifies the correct placement of pieces. You must account for edge constraints (the perimeter of the puzzle must have 'flat' edges) and implement a search strategy to place pieces one by one.

Requirements

  1. Define a data structure to represent a Piece that can be rotated 90 degrees.
  2. Implement a solve(pieces) function that returns a 2D grid of pieces if a solution exists, or null otherwise.
  3. Include a mechanism to handle potential duplicate pieces (pieces with identical shapes).

Example

Input: A list of 4 pieces, where each piece is represented by a tuple of 4 sides: (top, right, bottom, left). Example Piece: (1, 2, 3, 0) where 0 denotes a flat edge.

Constraints

  • The grid size is fixed at N x M.
  • Pieces can be rotated 0, 90, 180, or 270 degrees.
  • The search space can be large; consider how to prune the search tree efficiently.
class Piece:
    def __init__(self, sides):
        # sides: list of 4 integers representing top, right, bottom, left
        self.sides = sides

    def rotate(self):
        # Rotate the piece 90 degrees clockwise
        pass

Hints

Hint 1

Start by modeling the constraints as a set of rules: a piece placed at `(r, c)` must be compatible with the piece at `(r-1, c)` and `(r, c-1)`.

Hint 2

Use a backtracking approach where you attempt to place pieces position by position, keeping track of used pieces in a frequency map to handle duplicates.

Hint 3

Prune your search early by validating the compatibility of a piece's edges with its already-placed neighbors immediately upon placement.

Follow-up questions

  • How would you modify your algorithm if the puzzle was not rectangular but had a free-form shape?
  • If the number of pieces is very large, what heuristics could you use to prioritize which piece to place next?
  • How would you handle a scenario where some pieces might be missing or corrupted, requiring an 'approximate' fit?