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:
- Move left or right to an adjacent empty square
- 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?