Can you place ten tetrominoes inside an 8x8 grid, such that they do not overlap or touch each other orthogonally (horizontally or vertically) ?
$\begingroup$
$\endgroup$
2
asked Jun 13, 2022 at 5:35
-
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
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
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.
answered Jun 15, 2022 at 15:12
$\begingroup$
$\endgroup$
8
what about the following arrangement of
8 T tetrominoes + 2 squares?
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
$\begingroup$
$\endgroup$
2
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