wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> The Canterbury Puzzle 2
        
(Message started by: rloginunix on Aug 23^rd, 2015, 10:56am)

Title: The Canterbury Puzzle 2
Post by rloginunix on Aug 23^rd, 2015, 10:56am

The Canterbury Puzzle 2, Frogs on Mushrooms

Though the original puzzle is termed in frogs and mushrooms let frog = coin and mushroom = square:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_cp02.png

The objective: swap the coins. Put the blue coins into the squares 6 and 8, put the green coins into the squares 1 and 3.

Rules:
- move only one coin at a time;
- no square can contain more than one coin at any time;
- coins can travel only along the designated lines connecting the squares;
- same color coins are indistinguishable;

Rules':
- a "move" = one square to a legal immediate adjacent square jump, e.g. 1 to 5;
Q1: What is the smallest number of such "moves" required to swap the coins?
Q2: What was your problem solving method?

Rules'':
- a "move" = any number of consecutive moves from Rules', e.g. 1 to 5 to 6 to 2 ... (subject to Rules);
Q3: How can you swap the coins in seven such "moves"?

Title: Re: The Canterbury Puzzle 2
Post by rmsgrey on Aug 23^rd, 2015, 1:13pm

You can also rephrase it as knights on a 3*3 chessboard.

A1: [hide]16[/hide]
A2: [hideb]Okay, my actual problem solving method on this was to look at it and think "obviously you do this" but, if I had to explain it to someone else, I'd put it like this:

The 8 squares form a cycle - you can either move from 1 to 7 to 3 to 4 to 8 to 2 to 6 to 5 to 1 or the same thing in reverse. You can redraw the diagram, swapping 2 and 7 and swapping 4 and 5 to make it look like a circle - at which point the solution should be obvious.

Since it's a closed loop with no branches, the 4 coins will always be in the same cyclic order, so it's just a question of moving each coin 4 times in the same cyclic direction to reach the opposite corner - obviously, you can't move the first one the whole way before moving the others out of the way, but so long as you keep moving them in the same cyclic direction and stop moving a given coin once it's moved 4 times, you'll always get there in 16 moves.[/hideb]

A3:[hideb]1>5
3>7>1
8>4>3>7
6>2>8>4>3
5>6>2>8
1>5>6
7>1[/hideb]

A4:[hideb]From above, we already know that it takes a total of 16 distance to move all 4 coins to their target positions, and that it doesn't matter which coin we move first - we're moving each coin to the diagonally opposite corner, so rotating the start setup by 90 degrees, playing out the same sequence of moves from the new positions, and then rotating by 90 degrees the other way would give the same final position, as would reflecting the starting position (effectively switching directions to go the other way) - also, time-reversing the moves will produce a valid sequence with the same effect.

So, if we want to minimise the number of moves, we want to maximise the distance each move covers (with overshooting the coin's destination).

So, first pick a cyclic direction to be "forwards", then for each move, pick a coin that can move the furthest in that "forwards" direction and move it that way as far as it will go without overshooting its destination.

The first coin will only be able to move one space, but it will leave a 2-space gap that the coin "behind" can move into for the second move, leaving a 3-space gap for the coin "behind" that to cross with the third move, and a 4-space gap the remaining coin can cross to reach its destination. The first coin now has a 4-space gap in front of it, but only needs to move three spaces to reach its destination, leaving a 3-space gap in front of the second coin which only needs to move two spaces, letting the third coin move one space of its two space gap to leave everything home.[/hideb]

Title: Re: The Canterbury Puzzle 2
Post by rloginunix on Aug 23^rd, 2015, 7:20pm

Top notch, rmsgrey. On all accounts. Nicely done.

(Historical remark: this puzzle seems to be pretty old, apparently it was first published in 1512)

Title: Re: The Canterbury Puzzle 2
Post by oceanvibe on Dec 3^rd, 2015, 1:31am

Nicely done, rmsgrey. No chance given to other members :))