# The swap puzzle

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?

• View this – Wen1now Jun 24 '17 at 9:35

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$$