There are $n$ blocks of O, X on each side of the board. Board is one dimensional, $2n+1$ squares. So it looks like this for $n=3$ case OOO*XXX (* is for an empty square) a block may be moved into an adjacent empty square, or it can jump one block to an empty square.
I want to find out the minimum moves to swap the places of the blocks. So for $n=3$ case, final position should be XXX*000
For my empirical try, it seems like the answer is $n^2+2n$ moves to swap the position. However, I cannot justify the answer. Do I have to use induction or any other argument? If so, please help me.
Each marker moves a total of $n+1$ spaces, so the total distance moved is $2n(n+1)$. If each move was a slide, this would mean there would be $2n(n+1)$ moves. However some of the moves are jumps. With some thought, you can convince yourself that the number of moves is $2n(n+1) -j$, where $j$ is the number of jumps.
Fortunately, we can determine $j$. For each of the $n$ X’s, and each of the $n$ O’s, there is exactly one jump between that X and that O. Therefore, there are $n^2$ jumps.