Packing Puzzles: The 70 Square and the Thirty Colour Cubes

Can you fit the squares of side 1, 2, 3 and so on up to 24 into one big square of side 70 ^[1]? Their areas add up to exactly 70 times 70, which makes the idea very tempting ^[1]. Yet the answer is no: the best possible packing leaves out the square of side 7, a result that took extensive computer search to prove ^[1].

This article explains why that puzzle is so famous, how mathematicians attack packing puzzles, and how a second puzzle, built from thirty painted cubes, turns packing into a game of matching colours.

What is a packing puzzle?

A packing puzzle gives you a set of pieces and a space, and asks you to fit the pieces into the space without overlaps. In the tidiest kind, the pieces fill the space exactly with no gaps, which is called a tiling. The 70 square puzzle asks for exactly that: a tiling of a square of side 70 by the squares of side 1 to 24 ^[1].

Packing puzzles are attractive because the rules are so simple. You can check any attempt by eye, and a single misplaced piece shows up at once as a gap or an overlap.

Why is the number 70 special?

The puzzle starts from a fact about numbers. If you add the squares 1², 2², 3² and so on, the running total is almost never a perfect square ^[1]. Since a 1918 result, it has been known that the only time it is, apart from 1 by itself, is when you stop at 24 ^[1]. The sum of the squares from 1 to 24 is exactly 70² ^[1].

So the areas match perfectly. Twenty-four squares with a total area of 4,900 could in principle fill a square of area 4,900 ^[1]. The question is whether their shapes can.

What happened when people tried?

According to a 2018 paper, the puzzle became widely known through a magazine column on mathematical games, and many readers sent in their best attempts ^[1]. Twenty-seven readers fitted every square except the one of side 7 ^[1]. Nobody fitted them all.

Later work showed that this is the best anyone can do. A computer search proved that no packing of these squares into the square of side 70 wastes less space ^[1]. The search treated the puzzle as a constraint-satisfaction problem: each rule, such as no overlaps and staying inside the frame, is a constraint, and the program tries placements one after another, backing out as soon as a rule fails ^[1]. It examined about 375 million partial placements and took 16 minutes ^[1]. An earlier article had reached the same conclusion with a related technique called backtrack programming, but left out the details because the arguments were so long ^[1].

Can the proof be done without a big search?

A 2018 paper set out to find a shorter, more human route to the same answer ^[1]. The idea is to start from the edges of the big square, because any tiling would have to line the edges with squares that fit along them exactly ^[1].

The paper proved a set of rules for any edge ^[1]:

• The squares of side 1, 2, 3, 4 and 5 cannot touch any edge ^[1].
• The squares of side 6, 7 and 8 cannot all sit on the same edge ^[1].
• If the square of side 6 is on an edge, the square of side 7 must sit right next to it on that edge ^[1].

These rules cut the work down sharply. An edge must be filled by squares whose sides add up to 70 ^[1]. Even the eight smallest squares allowed on an edge, from side 6 to side 13, add up to more than 70, so an edge can hold at most seven squares, and with the other rules the most is six ^[1]. The fewest is four, because even the three largest squares, 24 + 23 + 22, only reach 69 ^[1].

A first computer listing of possible edges, made before the rules were applied, had 9,285 entries ^[1]. Applying the rules cut the list to 391 ^[1]. The paper then showed by careful case analysis that one of these, an edge made of the squares 9, 14, 23 and 24, can never be part of a complete frame ^[1]. The authors described this as a step towards a complete proof by hand, and showed how the same approach could rule out other edges ^[1].

How do you think about a packing puzzle yourself?

This puzzle shows several ideas that help with any packing puzzle:

1. Check the area first. If the pieces cannot cover the space by area, no arrangement will work. If the areas match, as they do here, the puzzle is worth trying.
2. Start at the edges. Pieces along the edges must fit together exactly, which gives strong rules early on.
3. Place large pieces early. Big pieces have fewer places to go, so placing them first cuts down the choices.
4. Look for pieces that cannot go somewhere. Ruling out positions is often easier than finding the right one.
5. Watch the small gaps. A gap narrower than your smallest remaining piece means you have gone wrong.

These steps mirror what the computer search and the 2018 paper did, just on a smaller scale ^[1].

What is the thirty colour cubes puzzle?

A different kind of packing puzzle uses cubes instead of squares. Take a cube and paint each of its six faces a different colour, using the same six colours every time. If two cubes count as the same whenever one can be turned to match the other, there are exactly 30 different cubes ^[2].

You can check that number yourself ^[2]. Whatever colour ends up underneath, any of the other five can face up. That leaves four colours for the band of four side faces. Spinning the cube on the table does not make a new cube, so pin one of those four colours to the front; the remaining three colours can then go round the band in six orders ^[2]. Five choices for the top times six orders round the side gives 30 ^[2].

How do the cubes pack together?

The puzzle is to pick one of the 30 cubes as a model and build a larger copy of it, two cubes wide, two deep and two high, using 8 of the other cubes ^[2]. Each outside face of the big cube must be a single colour that matches the model. Inside, every pair of touching faces must share the same colour, a rule known as the domino condition ^[2].

It turns out that every one of the 30 cubes can be copied this way ^[2]. A 2018 paper showed how to find the eight cubes quickly ^[2]. The 30 cubes are set out in a grid of six rows and six columns, with the six squares on the main diagonal left empty ^[2]. Label the rows A to F and the columns a to f. To copy the cube in row A and column b, swap the letters: you use the cubes in row B and in column a, leaving out the cube at row B and column a itself ^[2]. That always gives exactly eight cubes ^[2].

Each copy can also be built in two different ways. Swap the top and bottom layers, give each cube a quarter roll and a quarter turn, and you get a second solution that is the first one turned 180 degrees ^[2].

What do these puzzles have in common?

Both puzzles start with a set of pieces that look as if they should fit, and both reward careful reasoning about edges and touching faces. In the 70 square, the areas match but the shapes refuse to cooperate ^[1]. In the colour cubes, the colours look random, yet a hidden pattern in the grid picks out a perfect set of eight every time ^[2].

Both puzzles also show how much a single rule can do. In the 70 square, the rules about which squares may touch an edge cut thousands of options down to a few hundred ^[1]. In the colour cubes, the domino condition decides how every inside face must meet ^[2]. Finding the rule that does the most work is often the real key to a packing puzzle.

They also show two ways to settle a puzzle. One is a large, systematic search by computer ^[1]. The other is a short argument that explains why the answer must be so ^{[1] [2]}. Both have their place in puzzle mathematics.

Try it yourself

You do not need special pieces to try these ideas.

• Cut squares of side one, two and three from squared paper. Their areas add up to fourteen. Can they fit inside a rectangle two cells high and seven cells long, which also has an area of fourteen? They cannot, because the largest square is too tall. Matching areas are needed, but they are never the whole story.
• Take a single cube and six colours. Paint it, then work out how many different cubes your friends could paint if each uses the same six colours once each.

If you enjoy fitting shapes together, the riddles below use the same kind of thinking.