problemmediumood

Object-Oriented Design for a Jigsaw Puzzle

MediumUpdated: Oct 16, 2025

Problem

Given an unordered set of jigsaw puzzle pieces, design data structures and an algorithm to assemble them into the final picture. Each piece has four edges; edges match only with their complementary partner and pieces can be rotated.

scattered pieces

assembled puzzle

Solution

1. Requirements Analysis

Functional requirements:

  • Model a puzzle piece with four edges and the ability to rotate (90°, 180°, 270°).
  • Represent edge types and determine whether two edges fit (complementary shapes: inner/outer or flat for borders).
  • Assemble pieces by matching complementary edges until the full solution is formed.

Non-functional requirements:

  • Efficiency: ideally build adjacency in O(N) to O(N log N) where N is number of pieces (edge hashing / maps are recommended).
  • Deterministic orientation: rotate pieces to a canonical orientation when connected.

Assumptions (from source):

  • Every edge fits with at most one complementary edge.
  • Puzzle is rectangular and pieces have four sides.

2. Use Case Diagram

Actor: Solver (human or algorithm)

Use case summary: The Solver inspects pieces, rotates them, and places them by matching edges until the puzzle is complete.

graph TD
	subgraph Jigsaw System
		UC1(Inspect Pieces)
		UC2(Rotate Piece)
		UC3(Match Edge)
		UC4(Place Piece)
	end
	Solver --> UC1
	Solver --> UC2
	Solver --> UC3
	Solver --> UC4

3. Class Diagram

Core classes and responsibilities (based on the provided pseudocode):

  • Edge: models an edge with Type (inner, outer, flat), a parent piece reference, and a fitsWith method.
  • Piece: holds four Edge objects (left, right, top, bottom) and supports rotation; tracks solvedOrientation.
  • Puzzle / Solver: container for pieces, maintains lists of inner/outer/flat edges and exposed edges, and drives the solve() process.
classDiagram
	class Edge {
		+enum Type { inner, outer, flat }
		+Piece parent
		+Type type
		+boolean fitsWith(Edge)
	}

	class Piece {
		+Edge left
		+Edge right
		+Edge top
		+Edge bottom
		+Orientation solvedOrientation
		+void rotate(int degrees)
	}

	class Puzzle {
		+Piece[][] pieces
		+Piece[][] solution
		+List~Edge~ inners
		+List~Edge~ outers
		+List~Edge~ flats
		+List~Edge~ exposedEdges
		+void sort()
		+void solve()
	}

	Piece "1" -- "4" Edge : contains
	Puzzle "1" -- "*" Piece

4. Activity Diagrams

Activity: Build edge map and sort pieces

graph TD
	A[Iterate all pieces] --> B[For each edge classify as inner/outer/flat]
	B --> C[If complementary edge already in map -> link and rotate]
	C --> D[Else add edge to map]
	D --> E[Continue until all edges processed]

Activity: Place matching piece (solve step)

graph TD
	X[Take exposed edge] --> Y[Find matching complementary edge]
	Y --> Z{Found?}
	Z -- Yes --> P[Rotate matched piece to align]
	P --> Q[Place piece in solution and update exposed edges]
	Z -- No --> R[Mark edge unresolved]

5. High-Level Code Implementation

Below are cleaned skeletons adapted from the original pseudocode. They show class structure and method signatures only.

Java

class Edge {
		enum Type { INNER, OUTER, FLAT }
		Piece parent;
		Type type;

		public boolean fitsWith(Edge other) {
				// returns true if this edge complements `other`
				return false;
		}
}

class Piece {
		Edge left, right, top, bottom;
		int solvedOrientation; // 0, 90, 180, 270

		public void rotate(int degrees) {
				// rotate piece edges and update solvedOrientation
		}
}

class Puzzle {
		Piece[][] pieces; // pool of remaining pieces
		Piece[][] solution; // assembled board
		List<Edge> inners, outers, flats;
		List<Edge> exposedEdges;

		public void sort() {
				// classify edges and identify corners
		}

		public void solve() {
				// iterate exposedEdges and try to match and place pieces
		}
}

Python

from __future__ import annotations
from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional

class EdgeType(Enum):
		INNER = 1
		OUTER = 2
		FLAT = 3

@dataclass
class Edge:
		parent: "Piece"
		type: EdgeType

		def fits_with(self, other: "Edge") -> bool:
				return False

@dataclass
class Piece:
		left: Optional[Edge] = None
		right: Optional[Edge] = None
		top: Optional[Edge] = None
		bottom: Optional[Edge] = None
		solved_orientation: int = 0  # degrees

		def rotate(self, degrees: int) -> None:
				# rotate edges and update orientation
				raise NotImplementedError

class Puzzle:
		def __init__(self) -> None:
				self.pieces: List[List[Piece]] = []
				self.solution: List[List[Optional[Piece]]] = []
				self.inners: List[Edge] = []
				self.outers: List[Edge] = []
				self.flats: List[Edge] = []
				self.exposed_edges: List[Edge] = []

		def sort(self) -> None:
				# classify edges and find corners
				raise NotImplementedError

		def solve(self) -> None:
				# main solve loop: match edges, rotate pieces, place them
				raise NotImplementedError

References

Comments