Friday, March 24, 2017

strategy - Hopping Frogs puzzle variant


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.




No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...