4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – KSmarts Jan 29 '15 at 20:14
  • $\begingroup$ @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. $\endgroup$ – Johannes Jan 30 '15 at 2:01
3
$\begingroup$

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

27 squares.

enter image description here

$\endgroup$
  • $\begingroup$ An obvious improvement presents itself... $\endgroup$ – Johannes Feb 1 '15 at 9:31
  • $\begingroup$ 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. $\endgroup$ – arbitrary Feb 1 '15 at 11:53
  • $\begingroup$ adjusted accordingly $\endgroup$ – arbitrary Feb 4 '15 at 22:25
  • $\begingroup$ @Johannes is that the obvious improvement you meant? $\endgroup$ – arbitrary Feb 5 '15 at 12:44
  • 1
    $\begingroup$ My solution is similar to yours (identical in graph theoretical terms). Will post an image in a separate answer. $\endgroup$ – Johannes Feb 6 '15 at 18:12
3
$\begingroup$

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

enter image description here

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):

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.