Thirteen convex tangrams

A tangram set is a square cut into seven pieces: two large triangles, a medium triangle, two small triangles, a square and a parallelogram. The puzzle is to rearrange them, all seven, flat and without overlap, into a given silhouette — a cat, a running man, a boat. Books of tangram figures, popular in Europe from about 1817 after sets arrived from China, ran to hundreds of silhouettes, and the number of figures the pieces can make is far larger than any book.

Among all those figures, which are convex — with no notch, no indentation, every corner pointing outward? The square the set came in is one. A triangle, a rectangle and a parallelogram are easy to find. In 1942 two mathematicians at Zhejiang University, Wang Fu Traing and Chuan-Chih Hsiung, proved that there are exactly thirteen. This essay recomputes the list. The method is the one that runs through the theory of dissections: find what every piece has in common, use it to reduce an infinite question to a finite one, and then try everything.

Every piece is made of one triangle #

Draw the tangram square turned on its corner and lay a fine grid over it, of squares the size of the tangram’s own square piece, each cut by its two diagonals. Every edge of every piece runs along a line of this grid, and every piece is a whole number of the right isosceles triangles that the grid’s diagonals cut each grid square into.

Take the small triangle as the unit; its legs have length 1 and its area is $1/2$. Then each large triangle is four units, the medium triangle, the square and the parallelogram two each, and each small triangle one. That is $2 \times 4 + 2 + 2 + 2 + 2 \times 1 = 16$ units, a total area of 8. Every edge of every piece is either a whole number in length, along the grid’s axes, or a whole multiple of $\sqrt 2$, along its diagonals, and every corner is a lattice point.

Why a convex figure stays on the grid #

A tangram figure in general need not respect any grid. Pieces can be turned through any angle and slid any distance, and a silhouette of a dancer has pieces at odd angles to each other. The key step of Wang and Hsiung’s proof was to show that convexity forbids this. In a convex figure the pieces fit together without gaps, every boundary edge is a straight run of piece edges, and every internal meeting of edges has to be filled exactly. They showed that this forces every piece onto a common grid of the kind in the second figure, possibly turned as a whole. The argument works through how the $45°$ and $90°$ corners of the pieces can meet along the outline and inside it; the outcome is that the sixteen small triangles of any convex tangram lie on one grid, side by side.

This is the step that makes the problem finite. Once the pieces are known to lie on a grid, a convex tangram is a convex polygon made of sixteen small triangles of that grid, with its corners at lattice points and its sides in the eight grid directions. There are only finitely many such polygons. The question splits into two: which convex grid polygons of area 8 exist, and which of them can be cut into the seven particular pieces.

Listing the outlines #

A convex polygon whose sides point in the eight grid directions has at most one side in each direction, and going round it anticlockwise the directions come in order: east, north-east, north, north-west, west, south-west, south, south-east. So it is described by eight lengths $a_0, \ldots, a_7$, with zeros for missing sides. Axis sides have whole-number lengths; diagonal sides have lengths that are whole multiples of $\sqrt 2$, and the multiples are what is recorded. The polygon closes if the steps add up to nothing, and the shoelace formula gives its area from its corners.

The listing chooses the first six lengths, solves for the last two from the closing condition, keeps the result if both are non-negative and the area is 8, and keeps one representative of every shape up to rotation and reflection, by comparing the length sequences under the eight symmetries of the grid. It finds twenty.

Several of the twenty are long and thin — a strip one unit wide and eight long, a diagonal strip, a long thin trapezoid. The others are compact: squares and rectangles, triangles, trapezoids, and various hexagons and pentagons with corners cut at $45°$. All twenty are honest convex polygons made of sixteen small triangles. The question is whether the seven pieces fit.

The search that decides each one #

Each candidate is tested by an exact-cover search. It is convenient to split each grid square into four quarter-cells by its two diagonals, because every piece, in every allowed position, is then a union of whole quarter-cells: the small triangle covers two, the square, parallelogram and medium triangle four each, the large triangle eight. A polygon of area 8 has 32 quarter-cells, and the seven pieces must cover each exactly once.

The search lists every position of every piece inside the candidate — all translations, and all eight rotations and reflections that keep the piece on the grid — as the set of quarter-cells it covers. It then fills the shape in a fixed order. At each step it takes the first quarter-cell not yet covered and tries every unused piece in every position that covers that cell without overlapping anything already placed. A dead end, where the first uncovered cell can take no remaining piece, sends it back to try the next option. When all 32 cells are covered, it has found an arrangement.

This is the same pattern of search that Donald Knuth made famous for polyomino puzzles. It is exhaustive: when it finishes with nothing, no arrangement exists. Thirteen of the twenty candidates have arrangements, exactly the thirteen of the first figure, and the other seven have none. That is Wang and Hsiung’s theorem, recovered by a computation that takes about a second.

Why the failures fail #

Four of the seven failures need no search. A strip one unit wide cannot hold a large triangle at all, since its legs are 2 long; the same is true of the other long thin shapes. The other three are more interesting, because each is compact enough that pieces fit into it in many ways — just never all seven at once.

In each of the three, the search’s best attempt places six of the seven pieces and leaves four quarter-cells, exactly the area of the piece still in hand. The gap is a shape of the right area that is not the shape of that piece, and no rearrangement of the six already placed makes it so. The figure shows only one dead end in each case, but the proof that the shape cannot be made is the whole search, every branch of which ends in some such gap. That is the character of an impossibility found by exhaustion: no single picture of a failure proves anything, and the proof is the record of having tried everything.

How many ways each can be made #

Stopping at the first arrangement answers whether a shape can be made. Letting the search run on counts the arrangements.

The counts run from 4 to 56. The square, the figure every set is sold as, has 8, which is a single arrangement seen in the eight positions its symmetries give. So the familiar square has, up to symmetry, exactly one solution — which is why reassembling a scattered tangram set into its box is harder than it looks. The rectangle of two by four units has 36 arrangements, and the most flexible shape, a hexagon, 56. A shape with little symmetry and many arrangements is easy to make by trial; a shape with much symmetry and one arrangement is the hard puzzle.

Four familiar shapes and nine strangers #

The four convex tangrams with ordinary names behave quite differently under the count. The right isosceles triangle with legs of 4 units — the shape of half the original square, scaled up — has 12 arrangements; its own symmetry, a single reflection, accounts for a factor of 2, so it has six genuinely different solutions. The rectangle two units by four has 36, and with four symmetries that is nine different solutions, the most of any familiar shape. The parallelogram with sides of 4 and $2\sqrt 2$ has 12, six up to its half-turn. The square has one.

The other nine have no common names: trapezoids with one or two corners cut at $45°$, pentagons, hexagons. The hexagon with 56 arrangements is a three-by-three square with its two lower corners cut off at $45°$ — a shape so accommodating that the large triangles can lie in it in several ways and the small pieces fill the rest almost at will. These nine shapes are, between them, most of what convexity allows; the familiar four are a minority of the list.

The asymmetry between the counts says something about how to solve tangrams by hand. A solver usually starts by placing the two large triangles, since they take half the area and have the fewest places to go. In the square they have essentially one position, and every other piece is then forced. In the 56-way hexagon the two large triangles can be placed in many ways, and most choices can still be completed. The search does the same thing implicitly: it fills the first uncovered cell, which in practice means it places the large pieces early and backs up rarely in the flexible shapes and often in the rigid ones.

Where the grid lemma fits among dissections #

Hinged dissections and dissections of squares into rectangles both have finiteness theorems of the same flavour as the tangram’s grid lemma: a structural condition on how pieces meet forces their edges to align, and then the possible configurations can be listed. Dehn’s theorem on rectangles tiled by squares is the cleanest example, where the alignment forces the side lengths to be commensurable. In the tangram the alignment is to a grid at $45°$ angles, and the commensurability is between 1 and $\sqrt 2$: every length in every convex tangram is a whole number plus a whole multiple of $\sqrt 2$, and the two parts can be counted separately.

How rare convexity is #

The figures that tangram books print are mostly not convex, and that is not an accident of taste. Convexity is a severe restriction on shapes made of pieces.

There is one convex polygon of area $1/2$, the small triangle itself; three of area 1; and the count grows slowly and unevenly, to 20 at area 8. The unevenness comes from parity: polygons whose area is a whole number can be built from whole grid squares in more ways than those whose area is a half-integer. All of these are tiny numbers compared with the count of all figures — convex or not, with or without holes — that sixteen small triangles can form, which runs into the millions.

This connects the tangram to the lattice polygons of Pick’s theorem, where area is counted by lattice points. Every candidate here has its corners on the lattice, and its area 8 could be read off from the points inside and on its boundary. The tangram adds a restriction that Pick’s theorem does not: the sides must run in only eight directions. Lattice polygons with sides in arbitrary directions are far more numerous, and the reflexive polygons with exactly one interior point, sixteen of them, are a different finite list of the same kind.

A dissection run backwards #

The tangram is a dissection problem turned round. The Wallace–Bolyai–Gerwien theorem says that any two polygons of equal area can be cut into the same finite set of pieces; the tangram fixes the pieces in advance and asks which polygons they reach. With pieces fixed, almost every polygon of area 8 is out of reach: the pieces can never make a circle, a regular hexagon, or any polygon whose sides are not in the eight directions. The reachable set is a thin, countable family, and its convex part is thirteen shapes.

There is a further surprise in the proof’s structure. The hard part is not the search, which a modern computer does in a second, but the lemma that forces the pieces onto a common grid. Without it there would be no reason to believe that the convex tangrams are finite in number at all, since pieces can be turned through a continuum of angles. That is the same shape of argument as Monsky’s theorem on cutting a square into triangles: a structural fact about all possible arrangements turns a question about the continuum into a question about whole numbers.

The grid lemma the search takes on trust #

The search confirms the second half of Wang and Hsiung’s argument, that exactly thirteen of the twenty grid polygons can be made. It does not confirm the first half, that a convex tangram must lie on a grid; that lemma is quoted, not recomputed, and a figure of thirteen shapes cannot show that no convex figure with pieces at irregular angles exists. Nor does the search treat pieces turned over: a tangram parallelogram is not symmetric under reflection, and the search allows it to be flipped, as tangram rules usually do. Forbidding flips would change some counts of arrangements, and it might change which shapes can be made.

The counts of arrangements depend on conventions — whether arrangements related by the shape’s symmetries are the same, whether identical pieces are distinguishable — and different conventions give different numbers. The counts here are one convention, stated in the caption.

Polygons enumerated, Wang and Hsiung quoted #

Computed here: every convex polygon with corners on the grid and sides in its eight directions, up to symmetry, for every area from $1/2$ to 8, by listing edge sequences and solving the closing condition, with 20 at area 8; the decomposition of the pieces into sixteen small triangles, with total area 8; every arrangement of the seven pieces in each of the twenty candidates, by exhaustive exact-cover search over 32 quarter-cells, giving 13 shapes with arrangements and their counts; and the deepest dead ends of the failures.

Quoted: Wang and Hsiung’s 1942 theorem, and in particular its lemma that a convex tangram lies on a grid; the history of tangram books.

Still open: what the pieces can make in general #

The convex figures are settled. The figures in general are not, in any useful sense. There is no known count of all the shapes, convex or not, that the seven pieces can form, even on the grid, and there is no simple test of whether a given silhouette can be made; deciding it is a search, and puzzles in this family are, in general, among the hard search problems. For other dissection puzzles the convex question has been asked and answered piecemeal — sets of polyominoes, the Stomachion of Archimedes, the five-piece and fifteen-piece variants of the tangram sold since — and each needs its own version of the grid lemma. Whether there is a general theorem that turns the convex shapes of any finite set of polygonal pieces into a finite computation is the question these cases raise, and it is not settled by any of them.

Twenty outlines, thirteen figures #

The seven tangram pieces are made of sixteen congruent small triangles, and Wang and Hsiung proved that any convex figure built from them lies on the grid of those triangles. That grid allows exactly twenty convex outlines of area 8, found by listing the eight edge lengths that close up. An exhaustive search finds an arrangement for thirteen of them and proves the other seven impossible — four too thin to hold a large triangle and three that always leave a gap of the right area and the wrong shape. The square, up to its own symmetry, can be made in only one way.