wu :: forums - Print Page


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

        riddles >> medium >> Couch Moving
        
(Message started by: James Fingas on Oct 21^st, 2003, 1:08pm)

Title: Couch Moving
Post by James Fingas on Oct 21^st, 2003, 1:08pm

Pictured below is part of the layout of an apartment, and a couch, currently outside the apartment. You have to try and get the couch into the living room (indicated).

After you have solved that, think about the following: how complicated could it possibly be to move a single object through an area, without being impossible? Do you need objects like tables in the way to make it difficult?

Title: Re: Couch Moving
Post by towr on Oct 21^st, 2003, 3:18pm

can we assume the couch is as two-dimensional as picture ? ;) cause then we can simply flip it on its side

::[hide]It seem possible to moves it through the kitchen, after first moving the table out of the way (into the living room), then taking the long way round. The place where the table used to stand (before we moved it out of the way) seems sufficient to turn the couch 90 degrees, and then shove it into the living room[/hide]::

on 10/21/03 at 13:08:17, James Fingas wrote:

After you have solved that, think about the following: how complicated could it possibly be to move a single object through an area, without being impossible? Do you need objects like tables in the way to make it difficult?

How about a maze :P
With trap-passages..
And with people guarding critical passages, who ask you riddles which you have to solve before they let you pass..
And moving objects which you have to avoid (like big axes slowly swinging back and forward).
And let's not forget side-quests, rescue the princess to get a key to answer the door of the shed where the shovel is located which you need to dig up the treasure the pirate asked for in exchange for a monkey which will help you steal an important document about the duck-conspiracy the major needs as proof, and in exchange for which he'll let down the drawbridge which you need to cross..

Title: Re: Couch Moving
Post by Icarus on Oct 21^st, 2003, 3:52pm

Actually, the original moving problem becomes much simpler if the door to a time traveling apartment appears temporarily at just the right location in the wall to allow you to open the door and gain the extra room needed to get around the tight corner. You must look for the holistic solution!

Title: Re: Couch Moving
Post by towr on Oct 22^nd, 2003, 12:44am

how is that holistic?

Of course you could also just break down the wall, it's a bit more feasable than time-travel.. Or make use of a third dimension (but not time). If the appartment is higher than the length of the couch you might me able to get it to the living room directly..

Title: Re: Couch Moving
Post by Icarus on Oct 22^nd, 2003, 9:35am

I was sure you in particular would have recognized that one! Would it have helped to add that the ultimate answer to this problem is 42?

Title: Re: Couch Moving
Post by towr on Oct 22^nd, 2003, 9:46am

I never actually read "hitchhiker's guide to the galaxy", I only know a few handfulls of references from it :P

Title: Re: Couch Moving
Post by BNC on Oct 22^nd, 2003, 10:19am

Just for the record -- this is not from THGTTG, but rather from "Dirk Gently's holistic detective agency"

Title: Re: Couch Moving
Post by towr on Oct 22^nd, 2003, 10:23am

Well, I never even heard of that one..
But I'll put it on my "to read before I die, maybe"-list ;)

Title: Re: Couch Moving
Post by aero_guy on Oct 22^nd, 2003, 10:24am

Wow, it sbeen a long time since I read that, is that how the couch problem they encountered occurred?

Title: Re: Couch Moving
Post by Rezyk on Oct 22^nd, 2003, 2:18pm

on 10/21/03 at 13:08:17, James Fingas wrote:

how complicated could it possibly be to move a single object through an area, without being impossible?

I imagine that it can get at least exponentially hard, as I can see reducing puzzle games like Spinout (pictured below) to a 2D couch problem with oddly shaped tables. Spinout is equivalent to the Chinese ring puzzle and has an exponentially large solution sequence.

Quote:

Do you need objects like tables in the way to make it difficult?

I would guess so -- without other moveable objects, you can try mapping the valid configuration space of the object (positions/rotations where it is not embedded in another object) and then determining its connectivity, which I think is not so hard.

Title: Re: Couch Moving
Post by James Fingas on Oct 23^rd, 2003, 9:30am

That's a fun puzzle. Of course it's just a grey-coded binary sequence in disguise (but aren't they all).

With tables, you could reduce the game to Sokoban (not sure it that's its original name). The one where you push square blocks around a maze. Very difficult.

But what about without tables? Could it be made difficult?

Title: Re: Couch Moving
Post by TimMann on Oct 23^rd, 2003, 11:11pm

Another interesting subclass of these puzzles is Rush Hour. It's PSPACE-complete, yet fun to play at parties. See:

http://www.sciencenews.org/20020817/bob10.asp
http://www.puzzles.com/products/rushhour.htm

Rush Hour has lots of "tables" (moving pieces). I have no idea about games that have an irregularly shaped area but only one moving piece.

Title: Re: Couch Moving
Post by Rezyk on Oct 24^th, 2003, 12:12pm

on 10/23/03 at 09:30:21, James Fingas wrote:

With tables, you could reduce the game to Sokoban (not sure it that's its original name). The one where you push square blocks around a maze. Very difficult.

Do you mean "you could reduce the game from Sokoban"? (showing that it's at least as hard as Sokoban)

If so, are you sure it can be reduced? The player's position, strength, and lack of pulling ability in Sokoban play major roles, disallowing many box movements for which there is free space. I assume those don't directly apply in the couch problem, where you can scramble across tables/couches to get to any position, coordinate a team of friends to move a dozen tables synchronously, and pull a table out of a damned corner. :)