Switcheroo and Hop-Over are versions of the classic Leaping Frogs puzzle, or Frogs and Toads puzzle. There is a row of 9 holes, and at the start four holes on the left are filled with marbles of one colour, and the four holes on the right with marbles of another colour, which leaves only the centre hole empty. The aim is to swap the two colours using only forward moves (moving a marble forwards by one hole) and jumps (jumping one marble over another so that it goes forwards a distance of two holes).
Versions of this puzzle exist with a different number of pieces, and it can be solved using any number of each colour. In the classic puzzle literature there are usually 3 of each in the shape of frogs. It was described in "Puzzles Old and New" by Professor Hoffmann in 1893, where it goes by the name "Right and Left Puzzle". Other names are "Jumping Frog Puzzle" and "Jeu des Grenouilles".
'Switch' is a puzzle by Mag-Nif. It has a board with tracks that connect nine peg locations. There are 8 pegs (four red, four green) that can slide along the tracks. The nine locations are arranged as a row of five, with a row of four underneath it. Each row is connected by a horizontal track, and each location on the bottom row is connected by diagonal tracks to the two nearest locations on the top row. The game starts with the colours separated and the space in the middle. The aim is to swap the colours in as few moves as possible.
It may not be immediately obvious how similar it is to the leaping frogs puzzle. Consider the diagonal sections of the track together as forming one long path. The pieces can slide forwards or backwards along that path. Moving a piece along a horizontal section is equivalent to going forwards or backwards two places in the path. This makes the puzzle equivalent to the frog jumping puzzle but without the restrictions of only moving/jumping forwards.
If your browser supports JavaScript, then you can play Switcheroo / the Leaping Frog Puzzle by clicking the link below:
Let a normal move to the left or right be denoted by L and R respectively. Left or right jumps will be denoted by LL and RR.
| Move numbers | Moves | Resulting position | |
|---|---|---|---|
| 1 | R |    |     |
| 2 | LL | | |
| 3 | L | | |
| 4-5 | RR RR | | |
| 6 | R | | |
| 7-9 | LL LL LL | | |
| 10 | L | | |
| 11-14 | RR RR RR RR | | |
| 15 | L | | |
| 16-18 | LL LL LL | | |
| 19 | R | | |
| 20-21 | RR RR | | |
| 22 | L | | |
| 23 | LL | | |
| 24 | R | | |
The structure of the solution above is quite obvious, made especially visible on the board of Mag-Nif's Switch. It can easily be extended to a solution for a larger number of pieces.
Let's consider the general case where there are m marbles of one colour and n of the other colour, on a board with m+n+1 holes. I'll write this case as (m,n).
The above information is enough to give you the complete solution if you can look two moves ahead. At any point during the solution there are at most two options (provided we already exclude jumping over a marble of the same colour). In the starting position both options are equally valid, and in most other cases one of the options immediately leads to a position that violates the conditions of the adjacency lemma. In the remaining cases with two options, the wrong move leads to a position where the only options left will violate the lemma. These rules for the cases with two available moves can be captured in a few simple patterns as shown below.
| Two move look-ahead: | ||
|---|---|---|
|
 |
|
|
|
|
| One option fails the lemma: | ||
|
|
|
|
|
|
| Both choices valid: | ||
|
|
|
|
|
|
Now let's examine the (n,n) solution more carefully, and see how it can be built up from smaller parts.
Suppose you start with an (n, n) puzzle in the starting arrangement. There is a sequence of moves and jumps that rearranges the marbles to a position where the blank space is at the right end, the marble at the left end has not moved yet, and the row of marbles alternates in colour. Let's call this sequence of moves Tn. It is illustrated in the picture below, together with its mirror image which I will call Tn'.
|
|
So now we have a position where the marbles are arranged so that the marble at one end hasn't moved, the marbles alternate in colour, with the empty spot on the other end. The n marbles of one colour (including the one that hasn't moved) can all jump forwards one by one so that you reach a similar position, but mirrored. The empty space is on the other end now, and the marbles still alternate in colour. Let's call this sequence of n jumps Sn. This, and its mirror image Sn' is shown in the next picture.
|
|
A solution for the (n,n) puzzle consists of Tn, followed by Sn, followed by the inverse of Tn'.
 |
 Tn |
|---|
|
| Sn |
|
| Tn' -1 |
|
While the sequence Sn is completely known, Tn is not, so we need to break that up into smaller steps. On an (n,n) puzzle we can apply Tn-1 and Sn-1 to the board excluding the outermost marble at each end. The single move of the loose outer marble, then brings the marbles into a fully alternating position, the end result of what Tn' would have done. Therefore for n>1, Tn is broken down into Tn-1', Sn-1', and a single move. T1 is just a single move.
|
|
With this breakdown, we can verify that this solution satisfies the move count theorem. Sn obviously consists of n jumps and no normal moves. Tn consists of one more move and n-1 more jumps than Tn-1. Since T1 has only one normal move, it is easily seen that Tn consists of n normal moves and 0+1+2+3+...+(n-1) = n(n-1)/2 jumps. The complete solution consists of one Sn and two Tn, so has 2n normal moves and n + 2*n(n-1)/2 = n2 jumps, as expected.
| Moves | Jumps | |
|---|---|---|
| Tn or Tn' | n | n(n-1)/2 |
| Sn or Sn' | 0 | n |
| Solution (n,n) = 2Tn+Sn | 2n | n2 |
If the number of marbles of each colour are different, then we can do a very similar breakdown. Let's assume that the colour with the fewest marbles (m marbles) starts on the left. We can apply Tm to it, simply by ignoring the rightmost n-m marbles. This time it does make a difference if it is done in mirror image or not, but both lead to a solution.
|
|
So we now have two possible arrangements of 2m alternating marbles and the space, with n-m marbles of the more abundant colour on the right. Applying Sm or Sm' followed by a single move shifts the arrangement one space to the right, past one of the abundant marbles. By doing this n-m times, the alternating arrangement reaches the right hand side.
|
|
At this point we just have to finish this in the same way as the normal (m,m) case, by doing Sm followed by the inverse of Tm' (or Sm' followed by the inverse of Tm).
Again we can verify that this solution satisfies the move count theorem. It consists of two applications of Tm, n-m+1 applications of Sm, and n-m normal moves. That gives 2m+n-m = m+n normal moves and 2m(m-1)/2 + (n-m+1)m = mn jumps, as expected.
It is interesting to note that the sequence of moves and jumps is palindromic if we ignore their directions. The beginning Tm matches the final Tm-1 (or Tm' -1), and in between those we have a sequence of applications of Sm/Sm' interspersed with single moves which is also palindromic.