Suppose you have a $n$x$n$ grid, and you place $k$ tiles on it at random, such that it is possible to rearrange the tiles into a pattern symmetrical about every major axis of the square grid (diagonals, horizontals and verticals).
My question is, in general, what is the number $a$, in terms of $n$ and $k$, such that given any random tiling of the grid, it can be restored to symmetry in no more than $a$ moves. I should clarify that a single move consists of swapping an empty square with an edgewise adjacent tiled square.
An example of a sequence on a $3$x$3$ grid is shown below:
In this example, $n = 3$ and $k = 4$. I have verified by hand that $a = 4$ is the minimum needed for these values to ensure a grid can always be restored to symmetry.
I've attempted to solve this problem by analysing every possible symmetry, for a specific value of $n$ and $k, $ and trying to use them to generate the initial starting configurations, such that after $a$ iterations of the generation, every possible starting configuration would be available in the generated set. However, this didn't seem to lead anywhere useful.
The issue I'm facing is, for larger values of $n$, the number of possible symmetries the square can have grows pretty fast, and the issue becomes choosing the right one such that the choice minimizes the moves needed to reach it. Is this problem feasible to solve in the general case, or does it depend on too many factors?
As a lower bound on $a$: Consider the pattern containing all squares below the diagonal of slope $-1$ on the square, and as many on the diagonal as we need to get a number of squares $k$ which is $0$ or $1$ mod $4$ (arranged symmetrically about the center of the square, for the sake of this argument - this can always be done).
Choose coordinates so that the center of the square is $(0,0)$. Then the center of mass of any symmetric pattern is $(0,0)$, while the center of mass of our chosen pattern is $(-1,-1)\cdot\frac{n^3-n}{12k}$. Since every move can bring the sum of the coordinates of the center of mass up by at most $0.5$, getting the pattern symmetric takes at least $\frac{n^3-n}6 = {n+1\choose 3}$ steps. This is attained by the example in the post.
As a trivial upper bound, moving any square to any other square takes at most $2n-1$ steps, and at most $n^2/2$ squares would need to be moved, so it can't take more than $n^3-\frac{n^2}2$ steps in total. Thus $a$ grows cubically. (I suspect the true value of $a$ is much closer to the lower bound here, and I wouldn't be surprised if it were exact.)