The swap puzzle

Question

The swap puzzle

Place small coins heads up on the squares marked H and tails up on the squares marked T. Swap the positions of the Heads for the Tails in as few moves as possible.

There are two ways to move a piece:

1. Move left or right to an adjacent empty square
2. Jump over a single adjacent piece into an empty space.

There are three increasingly larger boards that get harder. It is possible to complete the first in 3 moves, the second in 8 moves and the third in 15 moves.

Here are the solutions for the first 3 cases:

I) Solution in 3 moves:

0)  T_H
1)  _TH
2)  HT_
3)  H_T

II) Solution in 8 moves:

0)  TT_HH
1)  T_THH
2)  THT_H
3)  THTH_
4)  TH_HT
5)  _HTHT
6)  H_THT
7)  HHT_T
8)  HH_TT


III) Solution in 15 moves:

0)   TTT_HHH
1)   TT_THHH
2)   TTHT_HH
3)   TTHTH_H
4)   TTH_HTH
5)   T_HTHTH
6)   _THTHTH
7)   HT_THTH
8)   HTHT_TH
9)   HTHTHT_
10)  HTHTH_T
11)  HTH_HTT
12)  H_HTHTT
13)  HH_THTT
14)  HHHT_TT
15)  HHH_TTT

Now, the question is how to generalize this to arbitrarily large case, what's the minimal number of moves for general case and how to make an algorithm for solving the general case in minimal number of moves? I'm failing to see some general rule although there is a notice in the puzzle saying "Harder problems can be made easier by tackling simpler version first, then generalising the solution." Any help?

Answer 1

The answer is $(n+1)^2-1$ (source and another source)

To get the number of moves, look at how many spaces each frog must move. Each frog moves $n+1$ spaces, so there are a total of $2n(n+1)$ spaces moved. There are $n^2$ jumps where a frog moves two spaces, so the number of moves is $2n(n+1)-n^2=n^2+2n=(n+1)^2-1$

To prove that a frog jumping another of the same color cannot be part of the optimum solution, assume it is a green frog. We then must have GG_ with other frogs in the row. How did we get here? The first G could have jumped backwards, but then jumping forwards undoes the move and we would be better without the pair. An R could have moved backwards, but then the front G should have jumped it and we would be farther along. Finally, a G could have moved forwards, but then we had GG_ before (one space to the right) and we look at the move before that."

-- Ross Millikan