# Dissecting a square

You are asked to dissect an $$N \times N$$ square into polyomino pieces such that each piece shares a 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.

EDIT / Bounty offer by Will Octagon Gibson:

Two answers have already been posted using 8x8 squares and 16 polyominoes.

I plan to award a bounty of 100 if a correct answer is posted using a smaller square or fewer polyominoes.

I plan to increase the bounty to 200 if a correct answer is posted using a smaller square AND fewer polyominoes.

These offers will expire on November 30, 2023 at approximately 11:59 p.m. (my time).

Good luck!

• Wasn't this proven by Gerhard in that other puzzle? Jan 26, 2015 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, 2015 at 8:39
• @Quark - Gerhard has proven that for $D=5$ you need to dissect into at least 12 pieces. Jan 26, 2015 at 9:38
• "and no piece has area exceeding N". Is this condition necessary? Sep 17, 2019 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. Jan 27, 2015 at 15:05

It is also possible with rectangles.

or

• Nice. Didn't see those. Jan 27, 2015 at 22:52

A near miss for $$D=5$$ and $$N=7$$, with $$12$$ polyominoes and largest area $$8$$ instead of $$\le 7$$:

The underlying $$5$$-regular connected planar graph is the icosahedral graph.

• +1 So close! Nice! Nov 25, 2023 at 18:39