(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)?
This explortion utilises many of the understandings established in my comment “Eureka!! – Squares Anyway” in which an x – y orientation was unnecessary because of the nature of length of sides.
I have chosen an 8 x 5 grid as an arbitrary base model around which all rectangles may be addressed. It is labelled x from A to H across the top and y = 1 to 5 downwards. The grid is then boldly divided horizontally between Rows 3 & 4 and vertically between Columns 3 & 4 and F & G. Cells B2 to E5 on the ‘diagonal’ are shaded as are cells D1 to G4. Also shade G1, H2 A4 and B5.
The visual pattern is repeated in multiples of 3 whether by column or row. Note that the ‘Diagonal’ beginning at A1 has an initial blank cell as the adjacency property is preserved by this arrangement. Similarly a ‘diagonal’ that would end as in the case of H5 also terminates with a clear cell.
Note too that the block of cells F3 to H5 is important in determining the final outcome.
To begin: For any multiple of 3 columns, every row will have an identical number of black cells, that being int(x/3). However the first cell of Row 1 is exempt and may be represented by the value of [-1] in a final calculation.
Black cells for all rows to column int(x) will be y* int(x/3) –1.
For additional columns (and there will be either 1 or 2) there will be int(y/3) black cells.
The remaining cells of those columns (part of the F3-H5 black) will be 1, 2 or 4, depending upon rows and columns in excess of the multiple of 3. Mod(x,3)*mod(y,3) will evaluate to 0, 1, 2 or 4.
The following are conditions and implications surrounding the F3-H5 block.
In Following Table:
Description is Columns (C), Rows (R), Multiple of 3 (Mlt_3)
Add – describes number of cells added for cells as generated within the F3-H5 block.
Shade describes shading for the condition.
Black is the Black Cells value to show in the formula.
Description Add Shade Black
1. C & R are Mlt_3 0 F3 = White -1
2. Only 1 C or R
of Mlt_3 added 0 F3 = Black 0
3. 2 C or 2 R Rows
of Mlt_3 added 0 F3 = Black 0
4. Both 1 C and
1 R added 1 G4 = White 0
5. 2 C & 1 R, or
1 C & 2 R added 2 G4 = Black +1
6. 2 C & 2 R are 4 G4 = Black
both added H5 = White +1
G4 = Black
So the formula looks like this:
Black Cells = y*int(x/3) + mod(x,3)*int(y/3) + [Cells of Condition].
Cells of Condition?
I can only see a Software Solution.
Because of the differences in Syntax, ‘Nesting’, etc, programmers need to manipulate this according to their programming language.
I define a variable “Cond_Cells”. This is the value [Cells of Condition] which would be calculated by a properly constructed programming module which evaluates the following 9 conditions:
1. If (mod(x,3) = 0 AND mod (y,3) = 0) then Cond_Cells = -1
Else If
2. If (mod(x,3) = 1 AND mod (y,3) = 0) then Cond_Cells = 0
Else If
3. If (mod(x,3) = 0 AND mod (y,3) = 1) then Cond_Cells = 0
Else If
4. If (mod(x,3) = 2 AND mod (y,3) = 0) then Cond_Cells = 0
Else If
5. If (mod(x,3) = 0 AND mod (y,3) = 2) then Cond_Cells = 0
Else If
6. If (mod(x,3) = 1 AND mod (y,3) = 1) then Cond_Cells = 0
Else If
7. If (mod(x,3) = 2 AND mod (y,3) = 1) then Cond_Cells = 1
Else If
8. If (mod(x,3) = 1 AND mod (y,3) = 2) then Cond_Cells = 1
Else If
9. If (mod(x,3) = 2 AND mod (y,3) = 2) then Cond_Cells = 1
Software Solution
