Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Fri Jul 25, 2014 9:51 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 21 posts ] 
Author Message
 Post subject: Athena puzzle
PostPosted: Tue Feb 02, 2010 8:32 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
OK, this is not actually a twisty puzzle, but some of you might be interested.

Some of you have seen my iPhone puzzle game, Subway Shuffle. Well, for several years I have been working on getting it mass produced in physical form. Finally, it is out! The company that produced it, Popular Playthings, chose to re-theme it. So now instead of moving subway cars to reach a goal, you move... archaeologists. Hey, that's the way they wanted it. But the puzzles are the same. We selected 50 of the best levels from the iPhone game. (Actually I think there are a few in there that are only on the Mac version, and not on the iPhone version.)

Image

The product page is here.

The way is works is as follows. You're trying to get the Chief Archaeologist, who is carrying the top half of an Athena statue, to the place where the bottom half is. But he has to move along the marked paths; what's more, because he is red, he can move only on the red paths, and only into an adjacent empty spot. All the other archaeologists have the same movement rules, each with their own color: blue can only move on blue, etc.

It turns out that these game rules can lead to very complicated, very compact puzzles. I've generated instances that fit on this game board requiring hundreds of moves to solve (though we didn't put any that hard in this set). The specific levels that made it into the set are the result of hundreds of hours of computer search to find "interesting" puzzles, plus a lot of hand selection.

The back story here is that this puzzle came out of my Ph.D. research on games and complexity.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Tue Feb 02, 2010 8:36 pm 
Offline
User avatar

Joined: Tue Jan 05, 2010 5:43 pm
Location: under the "z" key
That is amazing. I am not going to be surprised if this is a best seller.

_________________
Image
http://www.youtube.com/user/EpicAbrewFail?feature=mhum
EAF on youtube!
2 invites to Jade club
PM me for invite


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Tue Feb 02, 2010 8:42 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
EpicAbrewFail wrote:
That is amazing. I am not going to be surprised if this is a best seller.

Thank you. Though I will be surprised if it's a best seller. I tried hard to get it produced by ThinkFun, the company that makes Rush Hour, TipOver, and several other games like that. They are in every game and toy store. I even made a physical prototype that enforces the color rules:

Image

But after three years of waiting, and having another company that wanted to produce it, I went with the other company. They don't have anything like the distribution network of ThinkFun, but hey, at least it's now out there.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Tue Feb 02, 2010 9:29 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
WOW!!!
bhearn wrote:
I even made a physical prototype that enforces the color rules:

Double WOW!!! I don't have an iPhone yet but I may be getting one soon. If I do I'll be sure to check this game out. It looks fun. I hope you can get them to offer a delux verson that enforces the rules. That prototype just looks so cool.
bhearn wrote:
It turns out that these game rules can lead to very complicated, very compact puzzles. I've generated instances that fit on this game board requiring hundreds of moves to solve (though we didn't put any that hard in this set).

The back story here is that this puzzle came out of my Ph.D. research on games and complexity.

Ok... now that is one defence I would have loved to sit in on. I can think of a ton of questions I would have asked.
(1) How many moves are required to solve the hardest board?
(2) How many boards are there that are "hardest"... i.e. requiring the same number of moves as the answer to question (1)?
(3) Do all the "hardest" boards have the same number of colors? If not, which have the fewest number of colors?
(4) Have you done a complete search of all possible boards? (this is needed to answer questions 1, 2, and 3)
(5) If not, is a complete seach of all boards possible with in a reasonable time frame with current PCs?
(6) If yes, how many unique solveable boards are there?

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Tue Feb 02, 2010 9:40 pm 
Offline
User avatar

Joined: Sun Nov 01, 2009 10:59 pm
Location: Blacksburg, VA
Cool game! Reminds me of the road coloring problem. The next time I'm at my local nerdy games store scoping out Catan expansions I'll check around for this one :).


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Tue Feb 02, 2010 10:40 pm 
Offline
User avatar

Joined: Sun Apr 16, 2000 3:17 pm
Location: Hong Kong
I saw this at the HKTGF and wanted to buy it. The distributors here for Popular Playthings are not the friendliest of people. They don't answer emails, and were quite frankly rude at the fair.

I wish you luck with the sales. As soon as I see this one online, I plan to purchase it.

_________________
Rox's Rambling Blog
Katsmom's Puzzling Videos


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 1:29 am 
Offline
User avatar

Joined: Fri Nov 04, 2005 12:31 am
Location: Greece, Australia, Thailand, India, Singapore.
katsmom wrote:
I saw this at the HKTGF and wanted to buy it. The distributors here for Popular Playthings are not the friendliest of people. They don't answer emails, and were quite frankly rude at the fair.

I wish you luck with the sales. As soon as I see this one online, I plan to purchase it.


Yeap, me and Rox had a nice look at that puzzle, but were not able to get it there.
It is very attractive especially to me (Greek theme LOL), so it is a matter of time
till I get it! I hope it goes well, it is a very interesting puzzle.

:)


Pantazis

_________________

Educational R&D, Gravity, 4D Symmetry, Puzzle Ninja, Matrix Mech, Alien Technology.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 1:37 am 
Offline
User avatar

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
Please make for Android!


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 2:07 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
wwwmwww wrote:
I hope you can get them to offer a delux verson that enforces the rules. That prototype just looks so cool.

That was really the sticking point with ThinkFun. Any mechanism we could think of that enforced the color constraints had two problems: (1) it cost too much to produce, and (2) it involved too much setup time to change levels. I don't anticipate them making such a version, especially since now that it's no longer subway cars, the sliding aspect is not quite as central to the theme.

Quote:
Quote:
The back story here is that this puzzle came out of my Ph.D. research on games and complexity.

Ok... now that is one defence I would have loved to sit in on. I can think of a ton of questions I would have asked.

Well, the thesis wan't about Subway Shuffle per se; it's just a problem that came up. It was about the computational complexity of whole families of games and puzzles -- in the same sense that, for example, the Traveling Salesman problem is NP-complete, if that means anything to you. (Subway Shuffle ought to be PSPACE-complete, but I haven't been able to prove it.)

Quote:
(1) How many moves are required to solve the hardest board?

The hardest one I found with the 10-station, triangular-grid layout takes 329 moves. I've found plenty of harder ones on larger grids, or by generalizing the rules: for example, allowing multiple colors per path segment (so either red or green could move on it, for example) allows much harder puzzles.

Quote:
(2) How many boards are there that are "hardest"... i.e. requiring the same number of moves as the answer to question (1)?

Only one that I could find.

Quote:
(4) Have you done a complete search of all possible boards? (this is needed to answer questions 1, 2, and 3)

No, the space is too large. My search algorithm basically consisted of starting with a random board, evaluating its difficulty, and then iteratively tweaking it in various ways, trying to increase the difficulty level. When no more improvements were possible, the program printed out the board (if it was over some difficulty threshold), and started over. Also I set parameters constraining the search in various ways: e.g. restricting the number of colors, the maximum vertex degree, etc. That let me generate puzzles with different flavors. But the unrestricted search would always, eventually, find that 329-move puzzle. Generally that took several hours.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 2:09 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
katsmom wrote:
I saw this at the HKTGF and wanted to buy it. The distributors here for Popular Playthings are not the friendliest of people. They don't answer emails, and were quite frankly rude at the fair.

That's not good. I'll make sure my contacts at Popular Playthings hear about it.

Quote:
I wish you luck with the sales. As soon as I see this one online, I plan to purchase it.

Thanks! It is now available online:

http://www.huntarcompany.com/mm5/mercha ... y_Code=PZZ

I haven't gotten my promo copies yet, so I don't know for sure that they're actually shipping. The order page is up, though.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 2:10 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
TBTTyler wrote:
Please make for Android!

I have too many other things on my plate at the moment to dive into Android development. But if any other Android developers out there want to port it, I'm open to sharing profits.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 2:17 am 
Offline
User avatar

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
bhearn wrote:
TBTTyler wrote:
Please make for Android!

I have too many other things on my plate at the moment to dive into Android development. But if any other Android developers out there want to port it, I'm open to sharing profits.

Now to learn Android development!


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 3:29 am 
Offline
User avatar

Joined: Sun Nov 25, 2007 7:29 am
Location: UK
I loaded Subway Shuffle onto my iPod a few weeks ago. I like this kind of puzzle such as Tipover, Stormy Seas etc. Particularly this one http://www.puzzlebeast.com/okra/index.html
It's great to see your idea being produced.

_________________
Website


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 8:32 am 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bhearn wrote:
The hardest one I found with the 10-station, triangular-grid layout takes 329 moves.


Is that board available in any of the formats? From what you said above its not in Athena. How about the iPhone or Mac version? Do you know of anyone that's solved it without the aid of a PC? If it doesn't have alot of dead ends it may not be all that hard.

And yes I was familiar with NP-complete... at least at one time. It's not a subject I've done much with and what exposure I've had was quite some time ago. Off the top of my head PSPACE-complete isn't ringing any bells though. I need to look this stuff up again as I enjoy reading out this stuff.

Carl

P.S. Would you be willing to share some details of your prototype? With some drawings I assume anyone could make their own out of wood. You might even be able to offer it printed on color in shapeways. Just some ideas.

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 11:00 am 
Offline
User avatar

Joined: Sat Jul 11, 2009 1:09 pm
Location: My House
This looks good. If I see it around I might buy it. :D

Alex

_________________
If I had £1,000,000 more, I'd be a Millionaire

YouTube Account: Cubiksrube113


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 11:13 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Very nice concept, congratulations for getting it to market. I hope it will be a big hit: the most addictive and successful games/puzzles are those with very simple/intuitive goals and rules, but increasingly complex levels of logic, so this is right on target!

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 11:22 am 
Offline
User avatar

Joined: Sun Apr 16, 2000 3:17 pm
Location: Hong Kong
Thanks for the link.
It is orderable at $19.99 I added 4 more that I saw at teh fair and wanted. For US$5 shipping, I couldn't resist :lol:

_________________
Rox's Rambling Blog
Katsmom's Puzzling Videos


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 12:54 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
wwwmwww wrote:
bhearn wrote:
The hardest one I found with the 10-station, triangular-grid layout takes 329 moves.

Is that board available in any of the formats? From what you said above its not in Athena. How about the iPhone or Mac version? Do you know of anyone that's solved it without the aid of a PC? If it doesn't have alot of dead ends it may not be all that hard.

Here it is:

Image

Actually I just remembered; properly the hardest should be 330 moves. For a while I had a constraint in my program that the first move never be forced. But that just tended to generate puzzles where there were two initial options, one of which is a one-move dead end; that's the case with this one. So from that dead-end spot it takes 330 moves.

I could send you a Mac version with all the levels. I've got a million versions of the program lying around; you'd have to give me a few days to sort them out. For a while I had the Mac version as a free download, but I had to take it down when I put the iPhone version out, otherwise I'd just get a ton of reviews like "Ripoff, man!!! DOn't pay for this, it's free online!!!" I did leave up a demo version, that has the first 15 levels. It's at http://www.subwayshuffle.com/ (as is a youtube video of the iPhone gameplay).

I've looked at the game tree for this level, and it's pretty messy. It's certainly not mostly forced moves. Yes, I know of at least one person who has solved it: Nick Baxter. He solved it on the iPhone version, which has a "backup" button; that does make it a bit easier than doing it with a physical version. The hardest thing is often remembering where you came from. Naturally I had to make an even harder version, just for Nick; that one has two multi-colored edges, and takes 589 moves. If he's solved it, he hasn't told me.

Quote:
P.S. Would you be willing to share some details of your prototype? With some drawings I assume anyone could make their own out of wood. You might even be able to offer it printed on color in shapeways. Just some ideas.

The prototype works by having disks attached to the tokens at different depths depending on the color; the track segments have matching grooves. Also the track segments are double sided, with a different color on the other side. That lets that one set of 19 segment pieces serve for most of the puzzles in the set.

Unfortunately part of the deal with Popular Playthings was signing over the rights to all physical versions of Subway Shuffle, so I couldn't put a version up on Shapeways. Had I known about Shapeways at the time I might have asked for an exception. It's possible they might not care about a version that's not called Athena and costs a lot more (as it would have to); I'll ask.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 1:00 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
katsmom wrote:
Thanks for the link.
It is orderable at $19.99 I added 4 more that I saw at teh fair and wanted. For US$5 shipping, I couldn't resist :lol:

Thanks! You might have wound up with some others I worked on. I did the computer analysis for Sink or Swim and Crossroads.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 4:32 pm 
Offline
User avatar

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
I've been enjoying this on my iPhone since IPP (I'm up to level 54, but I'm a stickler and don't move on until I solve it in the minimum number of moves).

I didn't know you had physically prototyped it and was thinking of an acrylic design essentially the same as you prototyped: Different depth tracks in layers of acrylic :)

Great job Bob!

Dave

_________________
Image
LitwinPuzzles.com has info on my puzzles.


Top
 Profile  
 
 Post subject: Re: Athena puzzle
PostPosted: Wed Feb 03, 2010 4:41 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
:( I wish I could play subway shuffle, but all I have is PC. :(

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group