RSS

King/Queen Puzzler

24 Jun

This is a puzzler that I got from someone a couple of weeks ago. It was quite interesting to solve it. Thought I will share the puzzler with you. If no one solves it, I will post the solution coming Tuesday…

Assume that there are 3 pairs of King/Queens in a shore. They have to cross this river with a boat which can accomodate a maximum of 2 people at a time. Following is the only rule that needs to be followed at either end of a shore: No Queen should be left alone (without her King) with another King (even if the other King’s Queen is around)…

Advertisements
 
13 Comments

Posted by on June 24, 2006 in From AM-KICKING blog

 

13 responses to “King/Queen Puzzler

  1. Mindframes

    June 26, 2006 at 6:55 pm

    Come on folks… did any of you try it? If you think it is rudimentary, it is wrong. If you think it is a prank, you are wrong again. The solution to this problem is based on pure logic…

     
  2. sdpal

    June 26, 2006 at 7:23 pm

    I tried and I assumed, any queen can travel alone and also travel with any other king in the boat.
    Heres the solution
    ———————————-
    side A [side B]

    k1q1, k2q2, k3q3 [__NONE__]
    (k1q1) -> leaves q1
    < - k1 goes back
    ———————————-
    k2q2,k3q3,(k1)
    (k1q2) -> k1q1 (stays)
    < - q2 goes back
    ———————————-
    k2q2,k3q3 [k1q1]
    (k2q2) -> k2 (stays)
    < - q2 goes back
    ———————————-
    q2,k3q3 [k1q1][k2]
    (k3q2) -> k3 (stays)
    < - q2 goes back
    ———————————-
    q2,q3 [k1q1][k2][k3]
    (q2,q3) -> Both stays
    ———————————-
    __None__ -> all pairs here
    ———————————-

    persons within [] are on sideB
    persons within () are travelling
    persons with no bracket on sideA

     
  3. Injikadan Mathai

    June 26, 2006 at 7:53 pm

    Here is some notation.

    Lets call them K1, K2, K3 and Q1, Q2, Q3 respectively. K1 is king 1 and his wife is Q1. Similar association for the others. Lets call the two shores Shore A and Shore B.

    Trip 1: K1 and Q1 move from Shore A to Shore B. Q1 is left behind on Shore B and K1 comes back to Shore A.

    Trip 2: K1 jumps off the boat on Shore A. Q2 and Q3 jump aboard and travel to shore B. Q2 is left behind on shore B and Q3 comes back on the boat to shore A. At this point. We have two queens on Shore B. Three kings on Shore A and one queen in the boat. Hence the condition is met.

    Trip 3: Q3 jumps ashore on Shore A. K1 and K2 board the boat and travel towards shore B. K2 disembarks and K1 and Q1 come back to travel back to shore A. Hence at this point we have K2 and Q2 on shore B. K3 and Q3 on shore A and K1 and Q1 in transit. Hence the condition is again met.

    Trip 4: Both K1 and Q1 disemabark at shore A. Now K1 and K3 board the boat and moves toward shore B. Both K1 and K3 diembark on shore B and Q2 boards the boat to move to shore A. At this point we have all kings on shore B, two queens on shore A and one queen in transit.

    Trip 5: Q2 disemabrks on shore A. Q1 and Q2 move back to shore B. Q1 and Q2 disembark. K3 boards the boat to move to shore A. At this point we have K1, K2, Q1 and Q2 on shore B. Q3 on shore A and K3 in transit.

    Trip 6: K3 and Q3 move to the other side.

    Hence we have achieved the objective keeping the constraint in mind. Do lemme know if this solution is ok

     
  4. Mindframes

    June 26, 2006 at 8:11 pm

    Shankar: In step2, you violate the condition that you cannot have 2 kings and 1 queen on one shore.

    Anup: U r right ! Good job!!

    I have a solution that can do it in 9 steps instead of 11. If you have more time, you can try it out…:)

     
  5. Injikadan Mathai

    June 26, 2006 at 9:52 pm

    @ Mindframes: thanks…whoa 9 steps..will look into that..

     
  6. sdpal

    June 27, 2006 at 12:46 am

    at either end of a shore: No Queen should be left alone (without her King) with another King

    dude, the queen is still on the boat.. (Tell the king, its dangerous to attack (!?) the queen on boat!).
    In step 2, k1 & q1 (who are a pair are in the shore, and q2 goes back in boat, leaving k2 in the shore B) Also, it has to be “k2q2,k3q3,[q1]”, instead of “k2q2,k3q3,(k1)

    Still, I beleive, mine is right.

     
  7. Mindframes

    June 27, 2006 at 2:07 am

    sdpal: One thing that is incorrect in your assumption is this.
    “No Queen should be left alone (without her King) with another King (**even if the other King’s Queen is around**)

    Following is my interpretation of your steps.

    [k1q1,k2q2,k3q3] [NONE]

    Step 1: k1q1 leave shore A
    [k2q2,k3q3] == [k1q1]

    Step 2: k1 goes back from shore B
    [k2q2, k3q3] =k1= [q1]

    Step 3:
    You show (k1q2) taking the trip. If you do that, the people in shore A are

    (k2, k3q3) while (k1q2) are in flight. The (k2, k3q3) combination is invalid. Am I missing something?

     
  8. Mindframes

    June 27, 2006 at 2:18 am

    sdpal:: sorry about that… the rule is that you can’t have a queen with 2 kings around even if she has her king… My bad.. I wasnt clear on that…

    You are right based on what you assumed. But the real problem doesnt allow you to have more kings than queens on any side.

     
  9. BrainWaves

    June 27, 2006 at 9:02 am

    K1Q1K2Q2K3Q3 –K1Q1-> K1Q1
    K2Q2K3Q3 < --K1-- Q1
    K1K2K3 –Q2Q3-> Q1Q2Q3
    K1K2K3 < --Q3-- Q1Q2
    K3Q3 —K1K2-> K1Q1K2Q2
    K3Q3 < --K2Q2- K1Q1
    Q2Q3 –K2K3-> K1Q1
    Q2Q3 < --Q1-- K1K2K3
    Q2 –Q1Q3-> K1Q1K3Q3
    K2Q2 < --K2-- K1Q1K3Q3
    –K2Q2-> K1Q1K2Q2K3Q3

     
  10. Mindframes

    June 27, 2006 at 2:26 pm

    Cool dude !! You nailed it !!!

    See if you can do it in 9 steps… If you look at your steps based on what you wanted to achieve to get to the result, you can reduce the number of steps…

     
  11. BrainWaves

    June 27, 2006 at 7:26 pm

    I found the 9 step solution in the morning, but could not reproduce it now.

     
  12. sdpal

    June 27, 2006 at 7:47 pm

    (I promise, I didnt look at the answer)
    k1q1 k2q2 k3q3 —k1q1–> NONE
    k2q2 k3q3 < --k1----- q1
    k1 k2 k3 —q2q3–> q1
    k1 k2 k3 < ---q3--- q1q2
    k3q3 —k1k2–> q1q2
    k3q3 < --k1q1--- k2q2
    q1 q3 —k1k3–> k2q2
    q1 q3 < --q2----- k1k2k3
    q1 —q2q3–> k1k2k3
    q1 < --k1----- k2q2k3q3
    —k1q1–> k2q2k3q3

     
  13. Mindframes

    June 28, 2006 at 1:02 am

    Cool SDPal !! Great job folks…

    Well, the 9 step solution is as follows:

    If you observe all your solutions, the key is to have the boat in shore A with K1,K2,K3 in shore A and Q1,Q2,Q3 in shore B (or vice versa). In step 3, we got it the other way around (the boat stays in Shore B) with K1,K2,K3 in shore A and Q1,Q2,Q3 in shore B. So, the reversal is the key.

    K1Q1,K2Q2,K3Q3 == NONE (Initial State)

    K1Q1 K2Q2 ==K3Q3==> (Step1)
    K1Q1 K2Q2< ==K3== Q3 (Step2)
    K1K2K3 ==Q1Q2==>Q3 (Step3)
    K1K2K3 < ==Q1== Q2Q3 (Step4)
    K2K3 ==K1Q1==>Q2Q3 (Step5)
    K2K3 < ==K1== Q1Q2Q3 (Step6)
    K3 ==K1K2==>Q1Q2Q3 (Step7)
    K3 < ==Q3== K1Q1K2Q2(Step 8)
    NONE ==K3Q3==> K1Q1K2Q2K3Q3 (Step 9)

    The reversal is done by just bringing a king in a dummy trip and returning it back.

    I used the traditional method of proving LHS=RHS by doing something from RHS and something from LHS and mangle around to solve it..:)

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: