Consider an $n$-by- $n$ board of unit squares for some odd positive integer $n$. We say that a collection $C$ of identical dominoes is a maximal grid-aligned configuration on the board if $C$ consists of $\left(n^{2}-1\right) / 2$ dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: $C$ then covers all but one square on the board. We are allowed to slide (but not rotate) a domino on the board to cover the uncovered square, resulting in a new maximal grid-aligned configuration with another square uncovered. Let $k(C)$ be the number of distinct maximal grid-aligned configurations obtainable from $C$ by repeatedly sliding dominoes.
Find all possible values of $k(C)$ as a function of $n$.
The answer is that
$$
k(C) \in\left\{1,2, \ldots,\left(\frac{n-1}{2}\right)^{2}\right\} \cup\left\{\left(\frac{n+1}{2}\right)^{2}\right\} .
$$

Index the squares by coordinates $(x, y) \in\{1,2, \ldots, n\}^{2}$. We say a square is special if it is empty or it has the same parity in both coordinates as the empty square.
We now proceed in two cases:
₪ा The special squares have both odd coordinates. We construct a directed graph $G=G(C)$ whose vertices are special squares as follows: for each domino on a special square $s$, we draw a directed edge from $s$ to the special square that domino points to. Thus all special squares have an outgoing edge except the empty cell.
Claim - Any undirected connected component of $G$ is acyclic unless the cycle contains the empty square inside it.

Proof. Consider a cycle of $G$; we are going to prove that the number of chessboard cells enclosed is always odd.

This can be proven directly by induction, but for theatrical effect, we use Pick's theorem. Mark the center of every chessboard cell on or inside the cycle to get a lattice. The dominoes of the cycle then enclose a polyominoe which actually consists of $2 \times 2$ squares, meaning its area is a multiple of 4 .
Hence $B / 2+I-1$ is a multiple of 4 , in the notation of Pick's theorem. As $B$ is twice the number of dominoes, and a parity argument on the special squares shows that number is even, it follows that $B$ is also a multiple of 4 (these correspond to blue and black in the figure above). This means $I$ is odd (the red dots in the figure above), as desired.

Let $T$ be the connected component containing the empty cell. By the claim, $T$ is acyclic, so it's a tree. Now, notice that all the arrows point along $T$ towards the empty cell, and moving a domino corresponds to flipping an arrow. Therefore:
Claim - $k(C)$ is exactly the number of vertices of $T$.

Proof. Starting with the underlying tree, the set of possible graphs is described by picking one vertex to be the sink (the empty cell) and then directing all arrows towards it.

This implies that $k(C) \leq\left(\frac{n+1}{2}\right)^{2}$ in this case. Equality is achieved if $T$ is a spanning tree of $G$. One example of a way to achieve this is using the snake configuration below.
Remark. In Russia 1997/11.8 it's shown that as long as the missing square is a corner, we have $G=T$. The proof is given implicitly from our work here: when the empty cell is in a corner, it cannot be surrounded, ergo the resulting graph has no cycles at all. And since the overall graph has one fewer edge than vertex, it's a tree.
Conversely, suppose $T$ was not a spanning tree, i.e. $T \neq G$. Since in this odd-odd case, $G$ has one fewer edge than vertex, if $G$ is not a tree, then it must contain at least one cycle. That cycle encloses every special square of $T$. In particular, this means that $T$ can't contain any special squares from the outermost row or column of the $n \times n$ grid. In this situation, we therefore have $k(C) \leq\left(\frac{n-3}{2}\right)^{2}$.

The special squares have both even coordinates. We construct the analogous graph $G$ on the same special squares. However, in this case, some of the points may not have outgoing edges, because their domino may "point" outside the grid.

As before, the connected component $T$ containing the empty square is a tree, and $k(C)$ is exactly the number of vertices of $T$. Thus to finish the problem we need to give, for each $k \in\left\{1,2, \ldots,\left(\frac{n-1}{2}\right)^{2}\right\}$, an example of a configuration where $G$ has exactly $k$ vertices.

The construction starts with a "snake" picture for $k=\left(\frac{n-1}{2}\right)^{2}$, then decreases $k$ by one by perturbing a suitable set of dominoes. Rather than write out the procedure in words, we show the sequence of nine pictures for $n=7$ (where $k=9,8, \ldots, 1$ ); the generalization to larger $n$ is straightforward.