8
$\begingroup$

Imagine you have a m x n grid which is initially colored white. you can fill in a cell with black color if and only if there are no immediately neighboring black cells (no black cells to the left/right/top/bottom). If you keep on filling cells you will eventually run out of legal cells to fill.

An example configuration is shown below. The green patterned ones are the only legally available spaces.

Example

What is the minimum number of black cells you can fill in the grid till you have no more cells you can legally fill? What is the best strategy to get this minimum?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Generally this answer will be around 20%, since every black square fills in four adjacent squares on average. Larger boxes will have a smaller average. $\endgroup$
    – user88
    Commented Apr 18, 2015 at 11:52
  • $\begingroup$ the result would be a checkerboard ! $\endgroup$
    – Abr001am
    Commented Apr 18, 2015 at 12:04
  • 3
    $\begingroup$ A checkerboard is the maximum black fill-ins. I need a minimum number of fills rather than the maximum. $\endgroup$
    – ahakarma seven
    Commented Apr 18, 2015 at 12:06

5 Answers 5

Reset to default
4
$\begingroup$

Follow these 5 steps in order. Only 1 of the steps will be done for any specific grid. The first 3 steps are the trivial cases, and steps 4 and 5 cover all other cases.

  1. If m=1 or n=1, then build like this. (Red blocks denote that the main pattern is altered, but it must be selected for coverage. Transpose if necessary.)

enter image description here

  1. If m=2 or n=2, then build like this. (Red blocks denote that the main pattern is altered, but it must be selected for coverage. Transpose if necessary.)

enter image description here

  1. If m=3 or n=3, then build like this. (Transpose if necessary.)

enter image description here

  1. If both m and n are even, then build like this, repeating the pattern shown for 4x4. (Red blocks denote that the main pattern is altered, but it must be selected for coverage.)

enter image description here

  1. If both m and n are not even, then build like this.

Careful: When m is odd and n is even (or vice versa), you must start the pattern coloring every other cell in a row or column with an even number of cells. If you do it the other way, then you are not guaranteed the optimal coverage.)

Careful: When m and n are both odd and m is not equal to n, you must start the pattern coloring every other cell on the shorter side. If you do it the other way, then you are not guaranteed the optimal coverage.)

enter image description here

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ For $5\times 5$, optimal is $7$, not $8$. $\endgroup$
    – RobPratt
    Commented Sep 6, 2020 at 2:12
  • 1
    $\begingroup$ @RobPratt- Thanks. Image corrected $\endgroup$
    – JLee
    Commented Apr 23, 2022 at 11:55
1
$\begingroup$

Here is how we can get $\approx (mn+2m+2n)/5$ tiles. Place the numbers $1$ through $5$ in each square as shown below: $$ \begin{array}{ccccccc} 1&4&2&5&3&1&\cdots\\ 2&5&3&1&4&2&\\ 3&1&4&2&5&3&\\ 4&2&5&3&1&4&\\ 5&3&1&4&2&5&\cdots\\ \vdots&&&&&\vdots&\ddots \end{array} $$ In words: the columns read $1,2,3,4,5$ periodically as you go down, and the pattern shifts down by 2 as you move right.

Now, color all $1$ tiles black. Then no more black tiles can be placed in the interior, because all numbers are neighbored by a $1$. The only place this breaks down is at the border: normally, a $2$ is covered by the $1$ tile above it, but $2$'s on the top border aren't covered. Same thing happens for the right, bottom and left border, with the numbers $3$, $5$ and $4$ respectively. Placing a black tile on each of these bad cases means no more can be placed.

Since there are about $\frac{mn}{5}$ ones, and about $\frac{m}{5}$ bad numbers on the left and right borders, and about $\frac{n}{5}$ on the top and bottom, my formula is as claimed.

This could be optimized further by initially coloring all of a different number black, instead of one, in order to minimize the bad cases.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The idea seems good but its probably not optimal. For example, the 4 x 4 case taken by another solution has only 4 points. Your solution would predict (4*4 + 2*4 + 2*4)/5 = 32/5 ~ 6 or 7 points ( how so ever you round it ). $\endgroup$
    – ahakarma seven
    Commented Apr 19, 2015 at 7:54
  • $\begingroup$ @ahakarmaseven I agree. Do you know of the optimal answer? Is there a nice solution? As far as I can tell, it boils down to messy casework based on the remainders of $m$ and $n$ mod 5. $\endgroup$
    – Mike Earnest
    Commented Apr 19, 2015 at 8:00
  • $\begingroup$ Coloring the "2" squares instead of the "1" squares increases the efficiency by not putting your first colored square in the corner, potentially reducing the number of extra squares on the sides. It also gives the exact pattern as the mdc32 answer. I think this gives the optimal solution for large m,n. $\endgroup$
    – user3294068
    Commented Sep 8, 2020 at 17:22
1
$\begingroup$

This is the independent domination number of the grid graph, that is, the smallest subset $S$ of nodes, no two adjacent, for which every node is in $S$ or adjacent to a node in $S$. The square version $m=n$ is in the OEIS, and the linked paper "Independent Domination of Grids" gives the complete results for all $m \times n$.

Improve this answer
$\endgroup$
0
$\begingroup$

One fill for larger boards is a pattern like the movement of a knight - I'm on mobile but I'll explain it as well as I can. 

..X.
X...
...X
.X..

This patter repeats in a 4x4 square - for larger boards, it is nearly optimal.

Improve this answer
$\endgroup$
6
  • $\begingroup$ How would this approach vary in the general case ( m x n, not necessarily even)? $\endgroup$
    – ahakarma seven
    Commented Apr 18, 2015 at 12:54
  • $\begingroup$ the problem is that knight path is solvable by graph theory , th op needs a specific algorithm working in all grides , graph theory or bruteforcing cant do anything $\endgroup$
    – Abr001am
    Commented Apr 18, 2015 at 15:26
  • $\begingroup$ @ahakarmaseven I don't know exactly - it is obviously optimal in cases where m and n are divisible by 4, but it is not necessarily optimal otherwise. I'll try and figure it out. $\endgroup$
    – mdc32
    Commented Apr 18, 2015 at 15:28
  • $\begingroup$ @Agawa001 this has nothing to do with a knights path or graph theory - I'm simply stating that the black squares are similar to the movement of a knight. $\endgroup$
    – mdc32
    Commented Apr 18, 2015 at 15:29
  • $\begingroup$ yes , it has things in common , knight path is relevant $\endgroup$
    – Abr001am
    Commented Apr 18, 2015 at 15:31
0
$\begingroup$

this is ...

  • a checkerboard by two lines step in case of :

-$n$ and $m$ are odd

  • knight shortest path in case of $4m*4n$ grid with supplementary adjustements

enter image description here

-if the grid is $4n*(4m+2)$ like the green framed rectangle or $4n*(4m+1)$ like brown rectangle or $4n*(4m+3)$ gray rectangle or $(4n+2)*(4m+2)$ blue rectangle the grid should be enlarged from supplementary same color-marked square which is located in the corner,the square is erased from old grid and marked in new grid square-corner.

-if the $(4n+1)*(4m+2)$ yellow grid is enlarged from the top we remove the yellow mark and place it at the top of new grid, if it is enlarged from right/left we add a new yellow mark.

-if it is the pink $(4n+3)*(4m+2)$ grid and enlarged from right side , two pink marks are removed and placed in the extreme right squares of new grid, if it is enlarged from top, just one mark is moved.

Conclusion: ($k$ is number of columns , $k'$ is n° of lines.)

for $(4k)$x$(4k'+2)$ grids number of black squares is $6(k*k')+1$

for $(4k)$x$(4k'+1)$ grids number of black squares is $5(k*k')+1$

for $(4k)$x$(4k'+3)$ grids number of black squares is $7kk'+1$

for $(4k+2)$x$(4k'+1)$ grids number of black squares is $9+6(kk'-1)$

for $(4k+2)$x$(4k'+2)$ grids number of black squares is $10+6(kk'-1)$

for $(4k+2)$x$(4k'+3)$ grids number of black squares is $12+7(k-1)+6k(k'-1)$

for $(4k)$x$(4k')$ grids number of black squares is $4kk'$

for $odd$x$odd$ the grid looks like an expanded checkerboard shown in picture above$**

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.