Square-free Grid

Let $r$ and $c$ be the row and column indices. Color $(r,c)$ black exactly when the bitwise AND of $r$ and $c$ is zero.

Both indices have $8$ bits. At each bit, the pair of bits may be $(0,0)$, $(0,1)$, or $(1,0)$. Thus there are $3^8=6561$ black cells.

Consider any square whose row and column indices differ by $d$. Take the least significant set bit of $d$. Exactly one of $r$ and $r+d$ has this bit set, and exactly one of $c$ and $c+d$ has this bit set. At the corner formed by these two indices, the bitwise AND is nonzero. Therefore that corner is white.

The time complexity is $O(256^2)$, and storing one output row takes $O(256)$ additional space.

Solution written by GPT6