Switcheroo / Hop-Over / Mag-Nif Switch / Leaping Frogs Puzzle (2024)

Switcheroo and Hop-Over are versions of the classic Leaping Frogs puzzle, or Frogs and Toadspuzzle. There is a row of 9 holes, and at the start four holes on the left are filled withmarbles of one colour, and the four holes on the right with marbles of another colour, whichleaves only the centre hole empty. The aim is to swap the two colours using onlyforward moves (moving a marble forwards by one hole) and jumps (jumping one marbleover 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 solvedusing any number of each colour. In the classic puzzle literature there are usually 3of each in the shape of frogs. It was described in "Puzzles Old and New" byProfessor 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 peglocations. 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 rowis 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 isto swap the colours in as few moves as possible.

It may not be immediately obvious how similar it is to the leaping frogspuzzle. 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 alonga horizontal section is equivalent to going forwards or backwards two placesin the path. This makes the puzzle equivalent to the frog jumping puzzle butwithout the restrictions of only moving/jumping forwards.

Solution:

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 theboard of Mag-Nif's Switch. It can easily be extended to a solution for a larger numberof pieces.

Further Analysis

Let's consider the general case where there are m marbles of one colour and n of theother colour, on a board with m+n+1 holes. I'll write this case as (m,n).

Jump Corollary:
A marble will never jump a marble of the same colour.

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 jumpingover a marble of the same colour). In the starting position both options are equally valid, and inmost other cases one of the options immediately leads to a position that violates the conditions ofthe adjacency lemma. In the remaining cases with two options, the wrong move leads to a position wherethe only options left will violate the lemma. These rules for the cases with two available moves can becaptured in a few simple patterns as shown below.

Two move look-ahead:
One option fails the lemma:
Both choices valid:

Order Corollary:
The order of the marbles of one colour remains the same.

Move Count Theorem:
In the solution to the (m,n) puzzle, there will be mn jumps and m+n normal moves.

Move Corollary:
In an (n,n) puzzle with n even, then every marble moves once and jumps n/2 times.

Backwards moves Theorem:
If the restriction on only moving pieces forwards is removed, then the standard solution is the shortest.For example, the shortest solution to the Switch puzzle is the same as the solution for the normal (4,4) puzzle.

Recursive solution for (n,n)

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 sequenceof 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 callthis sequence of moves T_n. It is illustrated in the picture below, together with its mirrorimage which I will call T_n'.

Tn

Tn'

So now we have a position where the marbles are arranged so that the marble at one endhasn'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 jumpforwards one by one so that you reach a similar position, but mirrored. The emptyspace is on the other end now, and the marbles still alternate in colour. Let's callthis sequence of n jumps S_n. This, and its mirror image S_n' is shownin the next picture.

Sn

Sn'

A solution for the (n,n) puzzle consists of T_n, followed by S_n, followedby the inverse of T_n'.

Tn
Sn
Tn' -1

While the sequence S_n is completely known, T_n is not, so we need to breakthat up into smaller steps. On an (n,n) puzzle we can apply T_n-1 and S_n-1 to theboard excluding the outermost marble at each end. The single move of the loose outer marble, thenbrings the marbles into a fully alternating position, the end result of what T_n' would havedone. Therefore for n>1, T_n is broken down into T_n-1', S_n-1', and asingle move. T₁ is just a single move.

Tn Tn-1' Sn-1' L

Tn' Tn-1 Sn-1 R

With this breakdown, we can verify that this solution satisfies the move count theorem.S_n obviously consists of n jumps and no normal moves. T_n consists of one moremove and n-1 more jumps than T_n-1. Since T₁ has only one normal move, it iseasily seen that T_n consists of n normal moves and 0+1+2+3+...+(n-1) = n(n-1)/2 jumps.The complete solution consists of one S_n and two T_n, so has 2n normal movesand n + 2*n(n-1)/2 = n² jumps, as expected.

Recursive solution for (m,n), m<n

If the number of marbles of each colour are different, then we can do a very similarbreakdown. Let's assume that the colour with the fewest marbles (m marbles) starts on theleft. We can apply T_m to it, simply by ignoring the rightmost n-m marbles. Thistime it does make a difference if it is done in mirror image or not, but both lead to asolution.

Tm

Tm'

So we now have two possible arrangements of 2m alternating marbles and the space, with n-m marbles of themore abundant colour on the right. Applying S_m or S_m' followed by a single move shiftsthe arrangement one space to the right, past one of the abundant marbles. By doing this n-m times, thealternating arrangement reaches the right hand side.

Sm L

Sm' L

At this point we just have to finish this in the same way as the normal (m,m) case, by doing S_mfollowed by the inverse of T_m' (or S_m' followed by the inverse of T_m).

Again we can verify that this solution satisfies the move count theorem. It consists oftwo applications of T_m, n-m+1 applications of S_m, 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 ifwe ignore their directions. The beginning T_m matches the final T_m^-1(or T_m' ^-1), and in between those we have a sequence of applications ofS_m/S_m' interspersed with single moves which is also palindromic.