6
$\begingroup$

There is an old puzzle which has various names such as Toads and Frogs, Jumping Frogs, Hopping Frogs, Leap Frog, etc., and which has been asked here before. I'd like to share a variant of this puzzle that I came up and which I haven't seen anywhere else.

There is a straight row of 9 squares (or lily pads if you prefer), each large enough to contain at most one frog. The middle square is empty, and there are 8 frogs on the other squares. The four frogs that start on the left can only move to the right, and the frogs that start on the right can only move to the left. The aim is for the two sets of frogs to pass each other so that they swap places.

In the original version of the puzzle, a frog can either walk forward one square or jump forward two squares, provided of course that the destination square is the empty one. So they start as:

AAAA.BBBB

The first few moves are:

AAA.ABBBB
AAABA.BBB
AAABAB.BB

and eventually, if you do things correctly, they end up as:

BBBB.AAAA

In my new variant, a frog can only jump forward two or three squares (i.e. jump over one or two other frogs to the empty square) - they cannot move forward just one square.

Question 1:
How can the two sets of four frogs pass each other using only forward jumps of two or three squares?

Question 2:
The same question, but now with a row of 13 squares and two sets of six frogs.

Further info:
I used a computer to search for solutions with other numbers of frogs. Whereas the original version can be solved with any number of frogs on the left and any number on the right, my variant seems to be unsolvable if the left and right numbers are different. When they are equal, it can be solved for 2+2, 4+4, 6+6, 8+8, 9+9, 10+10, 11+11, and 12+12 frogs, but I have not searched further. Though I have not yet examined the optimal solutions very closely, at first glance there is no obvious pattern to them so I do not know if a general optimal solution is possible. There may well be a general solution that is not optimal in all cases.
I expected such an obvious variant to have been analysed before, but if so, I haven't found it.

Edit::
It turns out that my computer program was buggy. The puzzle can be solved when the number of frogs on each side differs, except for a few cases. I re-analysed the cases with up to 12 frogs on either side, and the only ones that have no solution are: 1+0, 1+1, 3+1, 3+3, 4+1, 4+3, 5+4, 5+5, 6+1, 6+3, 7+4, 7+7, 9+1, and 9+4.
There is a general solution for even numbers of frogs. Thanks to astralfenix for the observation that led me to it. For 2r+2s frogs it uses r+s+3rs moves, which is not quite optimal in all cases.

$\endgroup$
  • $\begingroup$ Is this the very same person that runs jaapsch.net? If so, I'd like to say that your website is extremely interesting and informative - have been following it for a while :) Thanks for running such a unique set of analyses. $\endgroup$ – TheGreatEscaper Dec 29 '16 at 9:30
  • $\begingroup$ @TheGreatEscaper: Yes, jaapsch.net is my site. On it there is one page about the standard version of the Hopping Frogs puzzle. $\endgroup$ – Jaap Scherphuis Dec 29 '16 at 9:43
2
$\begingroup$

Answer:

here's a way to do it in 33 moves for the 6 frog case. Interestingly, this involves putting the frogs in an alternating doubles pattern, 11221122 etc. The solution to the original version of the puzzle involves use of an alternating singles pattern (121212 etc).

enter image description here

$\endgroup$
  • $\begingroup$ "In my new variant, a frog can only jump forward two or three squares (i.e. jump over one or two other frogs to the empty square)" is noted, so you cannot move forward I guess... $\endgroup$ – Oray Dec 29 '16 at 9:34
  • $\begingroup$ Yes, moving one step forward is not allowed in my variant. $\endgroup$ – Jaap Scherphuis Dec 29 '16 at 9:39
  • $\begingroup$ Good observation about the 11221122 doubles pattern. I think that gives rise to a general solution for n+n frogs with n even. $\endgroup$ – Jaap Scherphuis Dec 29 '16 at 10:16
2
$\begingroup$

Question 1

Initially AAAA.BBBB:

  1. AA.AABBBB
  2. AABAA.BBB
  3. AAB.AABBB
  4. AABBAA.BB
  5. AABBAABB.
  6. AABBA.BBA
  7. AABBABB.A
  8. AABB.BBAA
  9. A.BBABBAA
  10. ABB.ABBAA
  11. .BBAABBAA
  12. BB.AABBAA
  13. BBBAA.BAA
  14. BBB.AABAA
  15. BBBBAA.AA
  16. BBBB.AAAA

So total 16 moves for the first try :)

33 moves for 6+6.

$\endgroup$
  • $\begingroup$ Well done. There could well be a general solution for even n that is of length n*n. However, the optimal solution that my computer found for 6+6 frogs is 33 moves. Maybe I should also search for non-optimal solutions if I want to find a general solution. $\endgroup$ – Jaap Scherphuis Dec 29 '16 at 9:51
  • $\begingroup$ @JaapScherphuis I will let u know when I put this into my computer too :) $\endgroup$ – Oray Dec 29 '16 at 10:00

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.