9
$\begingroup$

You can choose from 4 colors to color every square of the following $10\times 10$ grid.

enter image description here

After you finish, I'm going to take a connected block with at most three colors away. Your goal is to minimize the number of squares I can take away. How should you color the grid?

Two squares are connected if they share a common side. The block in the upper right quadrant is connected, the one in the lower left is not, because the green and blue squares share no common side with any other squares.

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Am I missing something, in this way, you can get all the squares but one? You can pick any 3 in a row or column and take it away. $\endgroup$
    – I'm Nobody
    May 26, 2022 at 10:17
  • $\begingroup$ @I'mNobody I can only take one connected block away. $\endgroup$
    – Eric
    May 26, 2022 at 10:24
  • $\begingroup$ I found that 3-color grids that are 6x6 and larger can be done with at most 8 squares. The optimal sequence for N>=1 is: 1, 3, 5, 6, 7, 8, 8, 8, ... $\endgroup$
    – Dmitry Kamenetsky
    May 30, 2022 at 11:02
  • 1
    $\begingroup$ For 4 colors and an $n \times n$ grid, the optimal sequence for $n \ge 1$ starts with $1, 3, 7, 9, 12, 13, 16, 16$. $\endgroup$
    – RobPratt
    May 30, 2022 at 13:15
  • $\begingroup$ yep that's what I got. For n=9 I got 18. $\endgroup$
    – Dmitry Kamenetsky
    May 30, 2022 at 14:52

3 Answers 3

Reset to default
10
$\begingroup$

Here's a solution that lets you take away at most

18 squares:

enter image description here
This solution tiles infinitely with a period of 8 horizontally and 6 vertically.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I got a checkmark already? Surely there must be some local improvements. $\endgroup$
    – Magma
    May 26, 2022 at 17:07
  • $\begingroup$ Local improvements？Why? $\endgroup$
    – Eric
    May 26, 2022 at 23:44
  • $\begingroup$ How do we know that this is optimal? $\endgroup$
    – Dmitry Kamenetsky
    May 27, 2022 at 4:28
  • $\begingroup$ @DmitryKamenetsky We don't. But it seems so. Let me uncheck it for now, in case someone comes up with a better idea, or prove this is optimal. $\endgroup$
    – Eric
    May 27, 2022 at 7:31
  • $\begingroup$ Seems optimal. Every single square is used for the purpose of creating its diamond-shaped "pen". Super efficient. $\endgroup$
    – JLee
    May 30, 2022 at 11:22
2
$\begingroup$

Well, this puzzle looks so cool. I wish I could skip work and continue messing with it, but I just had 20 minutes. The best I see so far is this.

enter image description here

where you will get

28 blocks by choosing red, green, yellow and taking the long diagonals.

I highly doubt this is optimal.

Improve this answer
$\endgroup$
2
$\begingroup$

I wrote a solver that finds approximate solutions using simulated annealing. The best solution I found has at most

18 squares

I found several solutions with the same score:

They all have a pattern similar to Magma's answer. For 9x9 the best I can do is also 18 squares, so I believe 18 for 10x10 is optimal, because it cannot be less than the 9x9 score.

2 2 0 3 0 2 2 1 3 0
1 0 0 3 2 0 1 2 2 3
0 1 3 2 3 1 0 1 3 2
0 3 1 2 1 3 0 3 1 2
3 0 2 1 2 0 3 0 2 1
3 2 0 1 0 2 3 2 0 1
2 3 1 0 1 3 2 3 1 0
1 1 3 0 3 1 2 1 3 0
2 2 2 3 0 2 1 0 0 3
3 0 3 2 2 0 0 1 3 2

0 1 1 2 3 1 3 1 0 2
1 0 3 3 2 1 3 0 1 1
1 3 0 2 1 2 0 3 0 2
3 3 2 0 1 0 2 3 2 0
0 2 3 1 0 1 3 2 3 1
1 2 1 3 0 3 1 2 1 3
2 1 2 0 3 0 2 1 2 0
0 1 0 2 3 2 0 1 0 2
1 0 1 3 2 3 1 0 3 3
2 3 3 1 2 1 3 0 3 2

2 3 3 0 0 1 1 2 2 3
3 2 0 3 1 0 2 1 3 2
2 0 2 1 3 2 0 3 1 3
0 1 1 2 2 3 3 0 0 1
1 0 2 1 3 2 0 3 1 0
3 2 0 3 1 0 2 1 3 2
2 3 3 0 0 1 1 2 2 3
2 2 0 3 1 0 2 1 3 3
1 0 2 1 3 2 0 3 1 0
0 1 1 2 2 3 3 0 0 1

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Can you share your code? $\endgroup$
    – I'm Nobody
    May 30, 2022 at 21:22
  • $\begingroup$ "approximate solutions using simulated annealing" . Can you explain your method in layman terms ? Secondly, any proof that this is optimal ? $\endgroup$
    – Hemant Agarwal
    Jun 23, 2022 at 11:54

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.