# Dissecting a square

You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares portion of its boundary with exactly $D$ other pieces, and no piece has area exceeding $N$. This can be achieved for $D \le 5$.

For $D=2, 3, 4$ the smallest such squares are of size $2 \times 2$, $3 \times 3$, $4 \times 4$, respectively: Find the smallest square for $D=5$.

Credit: inspired by this puzzle.

• Wasn't this proven by Gerhard in that other puzzle? – Quark Jan 26 '15 at 7:31
• That answer is not a square, and it can't be trivially extended to a square, because you will have pieces with an area larger than N. – dmg Jan 26 '15 at 8:39
• @Quark - Gerhard has proven that for $D=5$ you need to dissect into at least 12 pieces. – Johannes Jan 26 '15 at 9:38
• "and no piece has area exceeding N". Is this condition necessary? – Dmitry Kamenetsky Sep 17 at 2:32

I think I've found a solution for an 8x8 square. I do not know if it is the minimum solution or how to prove that: It was definitely fun to try and find this! Took me a while. Excellent puzzle.

Some comments on how I got to the solution (Rather a chronology than a full deduction):

- It has been proven in the other puzzle that at least 12 tiles would be needed.
- It was clear, that each piece has to have at least 2 squares.
- I was intuitively convinced that the solution would have a 4-fold rotational symmetry. (No proof for that whatsoever. More a 'feeling'.) So I set out with trying patterns in this symmetry. If I get 1/4th of the pieces in place, the other 3/4th would be correct automatically.
- I figured the rim would be the difficult part, as long-stretched tiles are needed, and their length is limited by the square-size.
- So I first tried to create a 7x7 square with fitting tiles to the border and leaving room for 5 connections. - This did not work out (because of the symmetry centre being 'left out'). So I then retried the same with a 8x8 grid, ending up with: - Trying to extend the colours towards the centre (always using 4-fold rotational symmetry on the extensions) I soon ran into obstacles, which forced me to 'shift' the outer rim to: - And then it was just a matter of extending inwards and realizing that the number of tiles is not yet enough. Adding 4 colours did the trick.

• Well done. This 16 pieces solution is almost certainly the minimum. There are alternative solutions with fewer pieces, but they typically have a 3-fold symmetry and require 3 pieces to cover the full boundary, thereby violating the requirement of the area not exceeding the linear dimension. Not a proof, but makes it pretty plausible smaller squares won't allow for a solution. – Johannes Jan 27 '15 at 15:05

It is also possible with rectangles. or • Nice. Didn't see those. – BmyGuest Jan 27 '15 at 22:52