1
$\begingroup$

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.

enter image description here

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?

$\endgroup$
  • $\begingroup$ View this $\endgroup$ – Wen1now Jun 24 '17 at 9:35
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Another source is my website where I prove various things about the general case. I also once posted a question here about a variant of that puzzle, which reminds me that I should revisit that post as I figured out some interesting things about it. $\endgroup$ – Jaap Scherphuis Jun 24 '17 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.