Consider a set of dominoes placed on an $ n \times n$ board, no touching allowed. Extend the board to $ (n+1) \times (n+1)$ by adding an empty column on the right and an empty row at the top. For each domino consider it's "shadow" which are all the squares lying directly above, directly to the right, or directly above and to the right of a cell covered by the domino. In the diagram below, the dominoes are the XX cells, and the shadows are designated by the dots. ... XX. .. X. X. It is clear that each domino has precisely $ 4$ shadow cells, and that different dominoes have disjoint shadows. The point of extending the board is that now even dominoes that were placed along the original right or top borders of the board have their full shadows. If there are $ 1004$ dominoes, then they cover $ 6 \times 1004$ cells (including their shadows), so the extended $ (n+1) \times (n+1)$ board must have area at least $ 6024 > 77^2$. Therefore $ n \geq 77$. If $ n=77$, we can achieve the required result by placing all the dominoes horizontally on the odd-numbered rows, having a single cell separating each domino from the next one. We can pack $ 26$ dominoes per row since $ 26 \times 3 - 1 = 77$, and they lie in $ 39$ rows, so overall we have $ 39 \times 26 = 1014$ dominoes, a bit more than necessary.