(First things first - I don't know a solution to this, but the puzzle occurred to me a few hours ago, and I thought people might be interested in it)
 
Imagine a rectangular (or square) grid of any size, every square white. If the grid is "x" squares across and "y" squares high, what is the minimum number of squares ("n") that must be shaded so that no white square is adjacent to more than 2 other white squares?
(For this puzzle, diagonally adjacent squares are not considered to be adjacent)
 
So, for example, if the grid is simply a 3x3 then the only square that needs shading is the centre one, then all others squares only touch two others - i.e. for x=3 y=3, n=1
 
a) Is there an formula to calculate "n" that will work for all paired-values of "x" and "y"?
b) If not, what is "n" for a chessboard-sized x=8 y=8 (post your suggested minimum using a standard chess-like "A7" type of description for a list of all your shaded squares)?

Well, for x = y = 2a + 1 for any natural number a, a solution (I don't know that it is the smallest solution) is to leave the outermost squares white, shade in the "ring" of squares on square away from the edge, leave the next "ring" white, etc. Your example of a 3 x 3 array, shaded square B2 is the second in the sequence. (The first is 1 x 1: a single white square, the third is 5 x 5 : shaded squares are B2,B3,B4,C2,C4.D2,D3,D4, etc.)

The same algorithm will work when x - b = y = 2a + 1, in effect "stretching" the center column to any number of columns (Symmetry holds when y is the larger number, so for the rest of this discussion I'll assume that y ≤ x)

When y is odd,as above, the "core" is a 1 x (b+1) array, which can be either shaded or white. but when y is even, the core is a 2 x (b +1) array, which if it is white, does not satisfy the conditions. There are two answers to this dilemma. Either start the alternate rings with a shaded core, instead of starting with a withe outer ring, or shade the A rank and then the remaining x by (y - 1) array has an odd y dimension.

I need to determine 1) if this algorithm does produce the smallest number of shaded squares in the y is odd case, and 2)which strategy produces the fewest shaded squares in the y is even case before I can say anything further.

Posted by TomM on 2002-07-22 06:28:46