We claim the number of ways to select $n^{2}-1$ such cells from a $(2 n-1) \times(2 n-1)$ grid is exactly $n^{3}$, which implies the answer to this question is 1000 . Partition the board into $n^{2}$ regions, as pictured. Also, shade red every cell in an odd row and column red, so there are $n^{2}$ red cells. Say a region is blank if it has no selected cell; normal if the selected cell is red; up-wack if the selected cell is above the red cell; and right-wack if the selected cell is to the right of the red cell. Note a $2 \times 2$ region could be both up-wack and right-wack. The key idea is that we have at most one blank region, which restricts things significantly. We have two cases: - Case 1: no wack regions. Then we pick a region to be blank, of which we have $n^{2}$ choices. - Case 2: some wack region. Note that (1) any region directly above an up-wack region must be either blank or up-wack; and (2) any region directly to the right of a right-wack region must be either blank or right-wack. In particular, there is at most one wack region (and we cannot have any up-wack and right-wack regions), since every wack region corresponds to at least one blank region. Suppose some region is up-wack. There are $n$ columns that could contain this up-wack region, and $\binom{n+1}{2}$ ways to pick an up-wack region and, optionally, a blank region above it. Similarly, there are $n\binom{n+1}{2}$ cases if there is some up-wack region, for a total of $2 n\binom{n+1}{2}$ choices. In total, we have $n^{2}+2 n\binom{n+1}{2}=n^{3}$ possibilities, as desired.
Compute the number of ways to select 99 cells of a $19 \times 19$ square grid such that no two selected cells share an edge or vertex.