Partition Grid Shapes into the Fewest Squares
Cover every unit cell exactly once with grid-aligned squares. Build a good partition, then separate the construction that works from the proof that no smaller partition can work.
Two shapes, two kinds of success
Your job: cover every occupied cell with squares that follow the grid lines. Each cell must be covered exactly once.
- The 68-cell shape, Missions 1–6: build a six-square cover, then learn why five or fewer squares cannot cover it. Here you will establish the minimum.
- The 181-cell shape, Missions 7–8: build any complete legal cover, count your pieces, and try to improve it. A 13-square example is available for comparison; this lesson does not establish the minimum for this larger shape.
A construction shows what can work. A minimum proof must also rule out every smaller piece count.
Cut only along grid lines
The worked example asks students to divide an irregular grid region into square pieces, using as few squares as possible. Every unit cell must belong to one piece, and every piece must be a genuine square.
A minimum needs two certificates
When the two bounds meet, the minimum has been proved.
Decide whether a proposed piece is legal
Turn the irregular outline into a row signature
Inspect one row at a time
Count occupied cells only. Row counts give the area, but do not specify where each row starts; use the drawn outline to place squares. Rows are numbered from top to bottom and columns from the left edge of the entire grid, including missing cells.
Test a square before committing to it
Choose a top-left cell and side length in grid units
Checking…
Cover the worked example region with six squares
Square-placement controls
Explain why “six works” is not yet the same as “six is fewest”
| A | A | A | |
| A | A | A | B |
| A | A | A | C |
The shown 3×3 choice leaves two cells, each needing its own 1×1 square: 3 pieces altogether. To test every possibility, also try the 1×1 and 2×2 first choices, repeating the same process on their uncovered cells. Every complete cover must belong to one of these branches.
The search below applies that idea to the 68-cell shape. “At most 5” means that each branch may use no more than five pieces in total. Mission 6 lets you explore the tiny example yourself.
Added exact-cover audit
We have a six-square construction. To establish that six is the minimum, the search checks every possible cover with five or fewer squares.
This search runs here, offline. It generates every grid-aligned square inside the shape. At each step it chooses an uncovered cell and tries every available square that covers it. Each complete cover must include one of those choices, so no cover is skipped. A branch stops when its piece allowance is used up. The five-piece search fails and the six-piece search succeeds. This is an added proof tool.
Join the two directions
Branch on the first uncovered cell
An exact-cover search can always choose the first uncovered cell. Every complete tiling must cover that cell with exactly one legal square, so testing those possibilities loses no solution.
Choose the square covering the top-left cell
Map the 181-cell practice shape
Read the rows before tiling
Build a complete partition of the large region and compare its piece count
Practice-board controls
Square-partition workshop
Correct all eight answers to complete the workshop. Areas count unit cells; side lengths count grid units.