Can you place ten tetrominoes inside an 8x8 grid, such that they do not overlap or touch each other orthogonally (horizontally or vertically) ?
-
1$\begingroup$ Another way of articulating this is to find an 8 x 8 pixel binary image for which performing connected-component labelling results in exactly 10 components of area 4. $\endgroup$– WyckJun 13, 2022 at 15:38
-
$\begingroup$ ok I'll wait then. But I can't give the tick to all 3... $\endgroup$– Dmitry KamenetskyJun 14, 2022 at 11:03
3 Answers
As promised, here are the three solutions that my computer found.
The first was already found by franck vivien (and Bass), the second by JLee.
what about the following arrangement of
I found it manually by searching arrangement of same pieces, then had to change a bit strategy
-
$\begingroup$ Well done! Can you find any other solutions? $\endgroup$ Jun 13, 2022 at 7:46
-
2$\begingroup$ I have confirmed by computer that there are two other solutions (ignoring rotation/reflection). If no one finds these, I'll post them in a day or two. $\endgroup$ Jun 13, 2022 at 10:32
-
1$\begingroup$ @JLee You are talking about the independent domination number. You might be interested in my answer to this closely related problem. $\endgroup$– RobPrattJun 13, 2022 at 15:11
-
3$\begingroup$ @JLee To see that $4$ is a lower bound for the independent domination number, note that no two of the following four tetrominoes can be blocked by a single tetromino: $$\begin{matrix} 1 &. &. &. &. &2 &2 &2 \\ 1 &1 &. &. &. &. &2 &. \\ 1 &. &. &. &. &. &. &. \\ . &. &. &. &. &. &. &. \\ . &. &. &. &. &. &. &. \\ . &. &. &. &. &. &. &3 \\ . &4 &. &. &. &. &3 &3 \\ 4 &4 &4 &. &. &. &. &3 \\ \end{matrix} $$ $\endgroup$– RobPrattJun 13, 2022 at 20:20
-
1
Now that I realize we don't have to use only T's, here is one solution:
-
$\begingroup$ Well done. This is the original solution I had in mind. Now there is one more solution left. Can you find it? $\endgroup$ Jun 13, 2022 at 22:11
-
1$\begingroup$ I tried for about 3 hours. Gotta take a break. Thx for the fun puzzle. $\endgroup$– JLeeJun 13, 2022 at 22:23