Packed in Tokyo - in a glass

Japanese popular culture.
User avatar
Oskar45
Posts: 2257
Joined: Mon Dec 05, 2005 2:35 am
Location: Vienna, Austria

Packed in Tokyo - in a glass

Unread postby Oskar45 » Mon Dec 03, 2012 4:37 am

Nobuyuki Yoshigahara [he died in 2004, aged 68] was one of the greatest puzzle inventors the world has ever known. Among his 200+ mechanical puzzles was a series of pieces designed for the Glass Puzzle Collection from Toyo Glass Company. While I do have the "Glass Puzzle Answer Book" [published by Ishi Press in 2011 - in Japanese and English], I would be interested to know whether these puzzles are still available in Japan and how difficult it would be to obtain them nowadays.

BTW, one of his puzzles [among the most popular of all time] is "Rush Hour". I don't know whether it's available under Android - but if you have an iPad/iPhone, get the full version. It costs less than €2.50 and gets you 2500(!) challenges...
Everyone loves a lover. Romeo loves Juliet. Therefore, Trump loves Putin.

User avatar
GL1zdA
Donor
Donor
Posts: 415
Joined: Thu Dec 31, 2009 3:18 pm
Location: Warsaw, PL

Re: Packed in Tokyo - in a glass

Unread postby GL1zdA » Mon Dec 03, 2012 5:05 am

Oskar45 wrote:BTW, one of his puzzles [among the most popular of all time] is "Rush Hour". I don't know whether it's available under Android - but if you have an iPad/iPhone, get the full version. It costs less than €2.50 and gets you 2500(!) challenges...


I played several variants of Rush Hour and I somehow didn't like it. While I could solve the puzzles through heuristics, it usually boiled down to finding a move you previously haven't seen. The way I solve it is similar to my approach to Sokoban or Vexed - discarding moves which are clearly wrong, imagining the endgame and trying to find the moves in between. On harder levels I add chains of moves which result in certain situation on the board. What's your way of finding a solution to Rush Hour puzzles?
:PI: :Indigo: :Indigo: :Indigo: :Indy: :Indy: :Indigo2: :Indigo2IMP: :Octane: :Fuel: :540:

User avatar
Oskar45
Posts: 2257
Joined: Mon Dec 05, 2005 2:35 am
Location: Vienna, Austria

Re: Packed in Tokyo - in a glass

Unread postby Oskar45 » Mon Dec 03, 2012 10:39 am

GL1zdA wrote:
Oskar45 wrote:BTW, one of his puzzles [among the most popular of all time] is "Rush Hour". I don't know whether it's available under Android - but if you have an iPad/iPhone, get the full version. It costs less than €2.50 and gets you 2500(!) challenges...


I played several variants of Rush Hour and I somehow didn't like it. While I could solve the puzzles through heuristics, it usually boiled down to finding a move you previously haven't seen. The way I solve it is similar to my approach to Sokoban or Vexed - discarding moves which are clearly wrong, imagining the endgame and trying to find the moves in between. On harder levels I add chains of moves which result in certain situation on the board. What's your way of finding a solution to Rush Hour puzzles?
I think you are a bit too optimistic :-)

Rush Hour [and Sokoban] are sliding-block puzzles. More than 45+ years ago, Martin Gardner wrote about such puzzles: "These puzzles are very much in want of a theory. Short of trial and error, no one knows how to determine if a given state is obtainable from another given state, and if it is obtainable, no one knows how to find the minimum chain of moves for achieving the desired state."

Well, even today there is no such theory - and there is a perfectly good reason for this: sliding-block puzzles have been shown to be PSPACE-complete. In particular, 10 years ago it was proved that Rush Hour is PSPACE-complete [that Sokoban is PSPACE-complete was shown in 1998].

HOWEVER, the above concerns only the generalized problems. It might indeed be possible to do better with smaller puzzles. The version I play on my iPad/iPhone [ThinkFun/BinaryArts] has a 6x6 board, the blocks are all 1x2 or 1x3 and each block constraint direction is the same as its lengthwise orientation [either horizontally or vertically]. The crucial block to be moved out of the grid [a red car] is always placed on the third row from top [actually, for the general case, even if the blocks are all just 1x2, Rush Hour is still PSPACE-complete]. The curious thing is that whenever I solve one particular puzzle, I'm always told whether or not I'd done so with *minimal* possible moves. This implies to me these guys indeed have an optimal algorithm at hand - I haven't yet figured it out, though...

So, peruse heuristics... :-)
Everyone loves a lover. Romeo loves Juliet. Therefore, Trump loves Putin.

User avatar
Oskar45
Posts: 2257
Joined: Mon Dec 05, 2005 2:35 am
Location: Vienna, Austria

Re: Packed in Tokyo - in a glass

Unread postby Oskar45 » Sat Dec 08, 2012 5:04 am

GL1zdA wrote:The way I solve it is similar to my approach to Sokoban or Vexed
Addendum to ^...

As I'd pointed out before, Rush Hour [and Sokoban as well] is PSPACE-complete. Vexed, on the other hand, is not only NP-hard but also in NP itself - so it's NP-complete. If you find a polynomial time algorithm for it, you will get very famous indeed - you'd not only crush SAT but also *every* other problem in NP as well :-)
Everyone loves a lover. Romeo loves Juliet. Therefore, Trump loves Putin.


Return to “Japan”

Who is online

Users browsing this forum: No registered users and 1 guest