Proof of shortest path to move a block from top-left to bottom-right in an $n\times n$ sliding puzzle Consider a 3x3 matrix:











X
O
O


O
O
O


O
O





Here the X is to move to the empty square by shuffling the board as a slide puzzle. I have failed to find a formal proof of what the fewest number of steps is, or what this puzzle is called.  Usually, slide puzzles aim for other things than switching corners, and path algorithms are exploring the number of paths, or the shortest such.
Here, a requirement is that there can never be two symbols in one square, and another piece needs to vacate it first.
The answer is $8*n-11$ where n is the dimension of the square grid.
I'm sure this fairly simple game has a name, and a nice paper too, I just can't find it.
 A: $\newcommand\X{\mathsf{X}}\newcommand\O{\mathsf{O}}$The $\X$ tile needs to be slid at least $2n-2$ times. Between each $\X$ slide, there needs to be some $\O$ slides. Specifically,

*

*If two consecutive $\X$ slides are in perpendicular directions, there needs to be at least two $\O$ slides in between. The optimal move sequence is some rotation/reflection/translation of the below picture:
$$
\begin{array}{|c|c|}
\hline \X& \\\hline \O &\O\\\hline
\end{array}
\stackrel{\text{$\X$ slides right}}\longrightarrow
\begin{array}{|c|c|}
\hline &\X \\\hline \O &\O\\\hline
\end{array}
\longrightarrow
\begin{array}{|c|c|}
\hline \O&\X \\\hline  &\O\\\hline
\end{array}
\longrightarrow
\begin{array}{|c|c|}
\hline \O&\X \\\hline  \O& \\\hline
\end{array}
\stackrel{\text{$\X$ slides down}}\longrightarrow
\begin{array}{|c|c|}
\hline \O& \\\hline  \O&\X \\\hline
\end{array}
$$


*If the two consecutive $\X$ slides are in the same direction, then there needs to be at least four $\O$ slides in between. I omit the diagram, because this situation is clearly less preferable to the previous; it is most efficient for the $\X$ to alternate between horizontal and vertical slides.
All that remains is to count up all of the required slides.

*

*There needs to be $2n-3$ initial $\O$ slides to bring the empty space from the lower right to a space adjacent to the $\X$.


*There need to be $2n-2$ $\X$ slides.


*There are $2n-3$ gaps between the $\X$ slides, each of which requires two $\O$ slides, for $4n-6$ additional required $\O$ slides.
All of that adds up to $8n-11$.
