Minimum cells to fill grid without consecutive neighbours

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. 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?

• 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. – Joe Z. Apr 18 '15 at 11:52
• the result would be a checkerboard ! – Abr001am Apr 18 '15 at 12:04
• A checkerboard is the maximum black fill-ins. I need a minimum number of fills rather than the maximum. – ahakarma seven Apr 18 '15 at 12:06

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.) 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.) 1. If m=3 or n=3, then build like this. (Transpose if necessary.) 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.) 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.) 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.

• How would this approach vary in the general case ( m x n, not necessarily even)? – ahakarma seven Apr 18 '15 at 12:54
• 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 – Abr001am Apr 18 '15 at 15:26
• @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. – mdc32 Apr 18 '15 at 15:28
• @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. – mdc32 Apr 18 '15 at 15:29
• yes , it has things in common , knight path is relevant – Abr001am Apr 18 '15 at 15:31

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 $mn/5$ ones, and about $m/5$ bad numbers on the left and right borders, and about $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.

• 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 ). – ahakarma seven Apr 19 '15 at 7:54
• @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. – Mike Earnest Apr 19 '15 at 8:00

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 -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\$**