Square-free Grid 2

Shuffle all cells and consider them in that order. Before adding a black cell at $(r,c)$, check only squares for which this cell is a corner. For every distance $d\geq1$, inspect the four directions $(\pm d,\pm d)$. If the other three corners of any such square are already black, leave this cell white.

Initially all cells are white. Every newly formed square is checked when a black cell is added, so no completed square has four black corners. If the resulting grid has fewer than $13100$ black cells, retry with another order. Print the grid upon reaching the target.

One attempt uses $O(256^3)$ time and $O(256^2)$ space. With $Q$ attempts, the total time complexity is $$.

Solution written by GPT6