# Puzzle pieces, each in contact with 5 others

You are asked to create puzzle pieces by joining together identical squares. This needs to be done such that the puzzle pieces can be arranged in a pattern with each piece being in contact with exactly 5 others. In terms of number of starting squares, how low can you go?

Background and further clarification

• Here we saw that 64 identical squares can be joined into puzzle pieces which can subsequently be grouped together in a square such that each piece is in contact with exactly 5 other pieces.
• Here we saw that 42 identical squares can be joined into puzzle pieces which can subsequently be grouped together in a rectangle such that each piece is in contact with exactly 5 other pieces.
• Now we are getting rid of the requirement to group the puzzle pieces into a specific shape: any shape will do!
• We still require two squares being 'joined' or two puzzle pieces being 'in contact' to mean that both share a finite portion of their perimeter.
• Also, the joining of the squares into puzzle pieces as well as the grouping of these pieces, is to be done within a plane and without creating any overlap. In other words, there should be no loss of total area covered: the resulting total puzzle needs to cover an area identical to that of the sum of the squares used.

So far this puzzle has seen zero attempts towards a solution. As long as progress is lacking, every one or two days I will publish a hint.

The first hint:

In contrast to the 64 square and 42 square solutions, the solution sought does deploy single square puzzle pieces.

• I think the 42 square solution might be optimal. It is based on the icosahedron graph, which is the smallest 5-regular planar graph. So if we abstract the problem to a graph, that is the optimal solution. I can't see any way of rearranging that answer to make it any smaller. Jan 29, 2015 at 20:14
• @KSmarts - graph theory tells us 12 puzzle pieces is the minimum. It doesn't tell us you need on average 3.5 squares per puzzle piece. A solution with fewer than 42 squares does exist. Jan 30, 2015 at 2:01

assuming a staggered grid isn't illegal because the expected solution includes single squares

27 squares.

• An obvious improvement presents itself... Feb 1, 2015 at 9:31
• The obvious (subjectively) one would be to shift the top row left or right half a square (making the row-staggering consistent) and remove the redundant top left or right (respectively) corner square. Feb 1, 2015 at 11:53
• adjusted accordingly Feb 4, 2015 at 22:25
• @Johannes is that the obvious improvement you meant? Feb 5, 2015 at 12:44
• My solution is similar to yours (identical in graph theoretical terms). Will post an image in a separate answer. Feb 6, 2015 at 18:12

Upon request, here is the solution I had in mind:

This solution is in essence the same as arbitrary's, as it is based on the same icosahedral graph (the smallest planar regular graph with vertex connectivity 5):