Notes
Requirements
Fix the scope first. The puzzle is a rectangle of R rows and C columns. Each piece has four edges, and each edge is flat, a tab that sticks out, or a blank that goes in. A tab locks only into a blank of the same shape. A player places a piece, turned any way, and the board rejects it if it does not fit. We detect a finished puzzle, and offer a solver and hints. Matching real photos is out of scope.
Ask the questions that change the code. Can a piece be flipped over? No, only turned in the plane, so four rotations. Are edge shapes unique? In our model each inner edge has its own shape number; with real photos shapes are only roughly unique, which is a follow-up. Can several people work on one board? Yes. And size matters: a few thousand pieces means trying every piece for every cell is too slow.
- a rectangle of R x C pieces
- each piece has four edges:
- flat, tab or blank
- a tab locks into a blank of
- the same shape
- place a piece, turned any way
- reject a piece that does not fit
- know when the puzzle is done
- a solver and hints
- out of scope: real images
- can pieces be flipped over?
- no, only turned in the plane
- are edge shapes unique?
- in our model yes; in real
- photos only roughly
- loose pieces on the table?
- only board cells matter
- many players at once?
- yes, one shared board
- size?
- up to a few thousand pieces
Entities
Underline the nouns: puzzle, piece, edge, side, board, cell. A piece has four edges. One design choice keeps everything clean: a piece never changes. Its rotation is not part of the piece but of where it is placed. So a placement is a piece plus a number of quarter turns, and the board holds a grid of placements. The same piece object can be tried in four rotations without copying it.
Class diagram
In code, an edge is a record of a type and a shape number. Its partner is the opposite type with the same shape, so tab seven pairs with blank seven. Two edges fit when one is the partner of the other, and a flat edge never fits anything. A piece is an id and four edges in a fixed clockwise order: top, right, bottom, left. Sides are an enum in that same clockwise order, which makes rotation simple arithmetic.
enum EdgeType { FLAT, TAB, BLANK }
enum Side { TOP, RIGHT, BOTTOM, LEFT }
record Edge(EdgeType type, int shape) {
Edge partner() // TAB 7 to BLANK 7
boolean fits(Edge o) {
return type != FLAT
&& partner().equals(o); }
}
record Piece(int id, List<Edge> edges)
record Placement(Piece piece, int rot) Rotation
Turning a piece clockwise once moves the top edge to the right side, the right edge to the bottom, and so on. So to ask which edge now faces a side, subtract the rotation from the side number, modulo four. With one turn, the edge now facing left is edge number two, the old bottom. No arrays are rebuilt, so trying all four rotations is free.
Edge edge(Side s) {
return piece.edges()
.get((s.ordinal() - rot + 4) % 4);
}
one clockwise turn: what was on
TOP now faces RIGHT
rot 1, side LEFT (3): edge 2,
the old BOTTOM
four rotations, zero copies Fit check
The board checks a fit by looking at all four sides. If the side faces outside the board, the edge must be flat, because the border is straight. If it faces another cell, the edge must not be flat, because a flat edge never points inwards. And if that neighbour is already placed, my edge must lock with its opposite edge. Place calls this check and throws if it fails, so the board can never hold a wrong fit.
Try the top-left cell. It needs flat edges on top and on the left, and real edges on the right and bottom. A corner piece turned the right way passes. The same corner turned upside down has its flat edges facing right and down, so it is rejected. An inside piece has no flat edges at all and fails on the very first side. The demo prints both rejections.
cell free and piece unused?
for each side s:
mine = p.edge(s)
outside the board:
mine must be FLAT
neighbour cell, empty:
mine must not be FLAT
neighbour placed:
mine.fits(their edge(s.opposite())) - needs: TOP flat, LEFT flat
- RIGHT and BOTTOM not flat
- corner turned the right way: ok
- same corner turned twice:
- flats face RIGHT and BOTTOM
- rejected
- an inside piece: no flats
- rejected on TOP
The naive search
The first idea is to fill each cell by trying every unused piece in all four rotations. That is what a person at a table does. For N pieces it costs roughly two times N squared fit checks. For twelve hundred pieces the demo counts almost three million checks. It works for a small puzzle, but the work grows with the square of the size, and the interviewer will ask you to do better.
for each cell:
for each unused piece:
for rot in 0..3:
if canPlace: place, next cell
N pieces: about 2 x N x N checks
1200 pieces: 2,880,486 checks
a person does the same thing:
pick up pieces until one fits Edge index
Here is the key idea. When we fill a cell, we already know at least one neighbour, so we know the exact edge we need: the partner of the neighbour's facing edge. So build a hash map once, from every edge to the pieces that have it and at which position. Finding the next piece becomes one lookup. With unique shapes, the list holds exactly one piece, so every cell costs constant time instead of a scan.
Walk one lookup. The left neighbour shows tab forty one on its right side, so we need blank forty one. The index says piece twelve has it as edge number one. That edge must face left, which is side three, so the rotation is three minus one, which is two quarter turns. One full fit check confirms the other sides, and we place it. No guessing at rotations at all.
record Slot(Piece piece, int edgeIndex)
Map<Edge, List<Slot>> byEdge
build: for each piece, each edge i
if not FLAT: byEdge[edge] += (p, i)
find(cell, toward known neighbour):
need = known.edge(opposite).partner()
for (Slot s : byEdge.get(need))
rot = (toward - s.edgeIndex) mod 4
if canPlace: return it - left neighbour shows TAB 41
- on its RIGHT side
- need: BLANK 41
- index: piece 12 has it as edge 1
- it must face LEFT (side 3)
- rot = (3 - 1 + 4) % 4 = 2
- canPlace confirms the other
- sides, then place
Strategy: solvers
Solvers are a Strategy, so the demo can run both and compare them. They share one outer loop, written once in an abstract base class, which is the Template Method pattern. Pick a corner piece, turn it so its flat edges face top and left, place it, and let the subclass fill the rest. On a non-square puzzle a wrong corner makes the board the wrong shape, so filling fails quickly and we try the next corner.
interface Solver {
boolean solve(Board b, List<Piece> p);
}
abstract class CornerFirstSolver:
for each of the 4 corners:
clear, place it at (0,0)
if (fillRest(...)) return true
IndexedSolver: index lookups
BruteForceSolver: try everything Flow: border first
The solver builds the border first, the way people do. From the corner it walks the ring clockwise: along the top row, down the right column, back along the bottom row and up the left column. Each cell knows the neighbour it came from, so each one is a single index lookup. The fit check makes sure flat edges face outward, and the last cell of the ring is checked against both of its neighbours.
top row: (0, 1..C-1), from LEFT right column: (1..R-1, C-1), from TOP bottom row: (R-1, C-2..0), from RIGHT left column: (R-2..1, 0), from BOTTOM each step: index.find(cell, side) canPlace also checks flats face out last cell checks both its neighbours
Flow: fill the inside
Then fill the inside row by row. For every inside cell the left neighbour is already placed, so we look up the partner of its right edge, and the fit check also confirms the top neighbour. On twelve hundred pieces the indexed solver needs about two thousand four hundred fit checks, against almost three million for brute force. That is linear work instead of quadratic.
for r in 1..R-2:
for c in 1..C-2:
find(r, c, LEFT)
canPlace also checks TOP
1200 pieces: 2,403 fit checks
against 2,880,486 brute force
O(N) instead of O(N squared) Completion
How do we know the puzzle is finished? Because place refuses any piece that does not fit, the board can only ever hold correct fits. So a full board is a solved board, and completion is just a count of placed pieces compared with rows times columns. That is constant time. The tests also run a slow verify that rechecks every shared edge, as an independent check of the fast path.
boolean isComplete() {
return used.size() == rows * cols;
}
place() never accepts a bad fit,
so a count is enough: O(1)
verify(): slow full scan,
used only by tests Hints
A hint reuses the same parts. If the board is empty, suggest a corner for the top-left cell. Otherwise find the first empty cell that touches a placed piece, look up the partner of that neighbour's edge in the index, and return the piece, the rotation and the cell. The player still has to place it, and the board still checks the fit, so a hint can never break the rules.
Observer
The board never prints. After each placement it notifies listeners with the cell, the placement and the count so far. A progress bar, a celebration screen when the count is full, and the screens of other players in a shared game all subscribe the same way. Listeners live in a copy-on-write list, so a new player can join while others are placing pieces.
Concurrency
With many players on one board, two people can drop a piece on the same cell at the same moment. Place is synchronized, so the fit check and the write happen together; the second drop sees the cell taken and is rejected. The used set stops the same piece being placed twice. For very large shared boards, you can lock per region or run each board as an actor with a queue of moves.
- place() is synchronized:
- fit check + write together
- second drop on the same cell:
- cell taken, rejected
- same piece dragged twice:
- used set rejects it
- huge boards: lock per region
- or one actor per board
Extensibility
Interviewers will push toward real images. Real pieces are scanned, so an edge holds a curve signature, not a clean number. Index by a coarse hash of that signature, then score the few candidates by shape and by the colours along the edge, and pick the best. Because two shapes can look alike, the solver may need backtracking. Timers and scores are listeners, and a saved game is just its list of placements.
- real photos: Edge holds a curve
- signature; index by a coarse
- hash, score the few candidates
- similar shapes: backtracking
- in fillRest
- image matching: colour along
- each edge joins the score
- timer and scores: listeners
- save game: list of placements
Testing
The full code is below the player. A cutter gives every inner edge a unique shape and a random tab side, and a scrambler shuffles the pieces and turns each one, both with a seeded random generator, so every run is identical. The demo rejects bad placements, takes three hints, solves a small puzzle, then solves a twelve hundred piece puzzle both ways and verifies both boards.
4 x 5 box: 4 corners, 10 border, 6 inside Rejected: piece 12 turned 0 does not fit Corner turned upside down fits? false Hint: piece 15 turned 0 at (0,0) Solved 4 x 5: complete true, verified true placed 300 of 1200 ... 1200 of 1200 30 x 40 indexed: 2403 fit checks 30 x 40 brute force: 2880486 fit checks both verified
Follow-ups
Expect follow-ups. Why is rotation not stored on the piece? So pieces stay immutable and can be tried in any turn. How do you find a piece fast? A map from each edge to the pieces that carry it. Why start with the border? Flat edges cut the choices sharply. And a square puzzle can come out turned as a whole; picking the corner by its picture fixes that.
- why is rotation not on Piece?
- pieces stay immutable
- how to find a piece fast?
- map from edge to pieces
- why start with the border?
- flats narrow the choices
- solved image upside down?
- pick the corner by picture
- pieces flipped over?
- eight orientations, mirror
Say it like this
Here is the short version to say out loud. A piece has four edges: flat, or a tab or blank with a shape number. A placement adds the rotation, so pieces never change. The board checks all four sides on every place. An index from each edge to the pieces that carry it finds the next piece in constant time, border ring first and then row by row. And since every place was checked, a full board means solved.
- "A piece is four edges: flat,
- tab or blank with a shape. A
- placement adds the rotation.
- The board checks all four sides
- on place. An index from edge to
- pieces finds each next piece in
- O(1): border ring first, then
- row by row. A full board
- means solved."