hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Puzzle Suggestions
Goto page 1, 2  Next
 
Reply to topic    hacker.org Forum Index » General Puzzles View previous topic
View next topic
Puzzle Suggestions
Author Message
adum



Joined: 19 Apr 2007
Posts: 391

Post Puzzle Suggestions Reply with quote
We've got three puzzles right now, and we have a couple more good ideas, but we're always interested in new puzzles people think would be great for the site. Have an idea? Share it!

Here's what goes into an 'ideal' puzzle:

    * Relatively simple to understand the rules etc.
    * Some kind of graphical representation of the puzzle will let it be played in a simple flash app
    * It's mathematical in nature -- ie, a computer can solve it
    * There's a good way to scale the puzzle -- typically by making the board larger, adding more pieces, etc. (less so is adding new rules, unless the rules can be defined in a way a computer can parse them). By scale, we mean that the difficulty increases, preferably exponentially, as the puzzle levels increase. (The Runaway Robot puzzle is a good example of a puzzle that doesn't scale particularly well.)
    * Puzzle levels can be generated by computer. (This stops people from sharing solutions to particular levels -- every user gets their own levels.) Generation must be relatively fast compared to solving, but does not necessarily have to be done in real time.
    * Easy way to check a solution on the backend, in sub-second time


Let us know your thoughts!

adum
Fri May 11, 2007 10:57 pm View user's profile Send private message Visit poster's website
ShardFire



Joined: 30 May 2007
Posts: 26
Location: United Kingdom

Post Reply with quote
Sokoban? Haven't thought about random generation of problems yet, at least not in such a way that the difficulty will increase in a way that we would expect... Must be a way to do it. And anyway, there are lots of suitable boards 'out there'.
Thu Jun 07, 2007 6:21 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
sokoban is a cool puzzle, but the main issue with it is that there already exist freely downloadable solvers. programs people have already put a lot of effort into, and they do a good job. so the joy of coming up with a cool new algorithm to solve a puzzle would probably not exist. generating boards is another possible challenge... but i think it's doable.

sokoban has been proven NP-hard, by the way. (many of our problems probably are. this isn't a problem in itself. you can still come up with really creative algorithms for np-hard puzzles.)

however, sokoban _variants_ are a very promising direction. there are a ton of ways to tweak or add rules to the basic sokoban game which change the gameplay significantly. so these things we've been thinking about... but haven't come up with anything firm yet.

thanks for the suggestion,
adum
Thu Jun 07, 2007 6:36 pm View user's profile Send private message Visit poster's website
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
adum wrote:

sokoban has been proven NP-hard, by the way.


A little stronger: it's complete for PSPACE. Smile

adum wrote:
(many of our problems probably are. this isn't a problem in itself. you can still come up with really creative algorithms for np-hard puzzles.)


To state the obvious: a good puzzle should probably be NP-hard. We don't really want a repeat of Runaway... although perhaps we ought to have a class of puzzles like that, where a clever algorithm can max them out and the point is to come up with that algorithm.

They should almost certainly be ranked differently, though; I probably shouldn't have a permanent #2 contributing just because I was the second person to code up a suitably fast poly time algorithm...
Fri Jun 08, 2007 3:01 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
Quote:
A little stronger: it's complete for PSPACE.


i don't really know the difference =/ should do some reading...

Quote:

To state the obvious: a good puzzle should probably be NP-hard. We don't really want a repeat of Runaway... although perhaps we ought to have a class of puzzles like that, where a clever algorithm can max them out and the point is to come up with that algorithm.


we thought the same thing at first, but then decided that in some ways it's nice to have some class of puzzles that can be 'won.' gives people a goal with a definite end.

Quote:

They should almost certainly be ranked differently, though; I probably shouldn't have a permanent #2 contributing just because I was the second person to code up a suitably fast poly time algorithm...


actually, you and everyone else who has solved 513 get the same number of points, so it's fine to be late to the party. this keeps it fair, i think. whenever two people have the same score, they get the same points.

adum
Sat Jun 09, 2007 3:01 am View user's profile Send private message Visit poster's website
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
adum wrote:
Quote:
A little stronger: it's complete for PSPACE.


i don't really know the difference =/ should do some reading...


Obligatory excess-detail:

P = "easy" (solvable in polynomial time)

NP = easy (=polynomial time) to check a proof. For example, for SAT, if the circuit is satisfiable you can prove it by providing a satisfying input.

PSPACE = polynomial space.

Note that P is contained in NP, which is contained in PSPACE. As such, PSPACE complete implies NP hard. (We actually do not know that P is smaller

When I say that Sokoban (or, to be precise, the set of winnable Sokoban positions) is PSPACE complete, I mean that (1) Sokoban can be solved in polynomial space and (2) any other problem that can be solved in polynomial space can be reduced to Sokoban in polynomial time.

It's kinda interesting that Sokoban is complete for PSPACE; the typical PSPACE complete problem is a two player game that isn't *too* hard; a solitare Sokoban game is as hard as many two player games. That said, what makes Sokoban so hard is that winning solutions could be exponentially large; given a polynomially bounded solution length it would fall down to NP. Smile

adum wrote:

actually, you and everyone else who has solved 513 get the same number of points, so it's fine to be late to the party. this keeps it fair, i think. whenever two people have the same score, they get the same points.


Great!
Tue Jun 12, 2007 3:03 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
JamesCFraser



Joined: 06 Jun 2007
Posts: 5

Post Reply with quote
So, seeing as 2DAs seem to be pretty popular, I saw a game a little while ago that I thought of an interesting puzzle for.

The game is called laser maze or something like that. In the game, you and your opponent put mirrors onto the board in order to get a beam of light around obstacles and into a goal. I don't know the rule for the two player version, but I thought up a nice way to make puzzles for one person.

Here's an example

Code:
* : Wall
. : empty space
\, / : mirrors
-, +, |, - light
e : emittor
g : goal

Puzzle:

(mirrors to place)
\\\\
////

Emittor fires ->

........
.e......
..***...
........
........
..*****.
....*..g
........

Solution:

........
.e---\..
..***|..
.....|..
./---/..
.|*****.
.\-\*/-g
...\-/..


I mainly suggest this because I would enjoy writing a puzzle generating algorithm for this puzzle, and thinking over the rules a little more to try and make the puzzle harder.

Anyway, I'm not sure if I'm even meant to make suggestions in this way Razz
________
Extreme Q Vaporizer


Last edited by JamesCFraser on Fri Feb 11, 2011 6:51 am; edited 1 time in total
Sun Jul 08, 2007 4:32 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
hey james, thanks for the idea! that does sound like that could be good. i guess you have to use all the mirrors, right? otherwise it could be easy.

if you come up with a good level-generating algo, let me know -- maybe we can use it.

cheers,
adum
Mon Jul 09, 2007 3:20 am View user's profile Send private message Visit poster's website
JamesCFraser



Joined: 06 Jun 2007
Posts: 5

Post Reply with quote
Hey

I can't think of a way to make the puzzles hard for the problem I suggested. They're actually all just very easy to solve. So, I think I may as well scratch that idea.

However, the fact there are some bot war puzzles is a pretty neat feature. I could certainly have fun thinking up insoluble games.

You could also have games like chess or go. Though, some people may be tempted to steal open source algorithms, which would be a shame
________
SWED


Last edited by JamesCFraser on Fri Feb 11, 2011 6:51 am; edited 1 time in total
Fri Jul 20, 2007 12:56 am View user's profile Send private message
MaxistXXL



Joined: 20 Nov 2007
Posts: 13
Location: Earth

Post Reply with quote
I came up with a good idea. The purpose is, to arrange and combine a collection of forms, so they fit into a big form.

Lets take, for example, a square. Then we split this square up, so we have got 4 triangels. Afterwards we rotate the triangles randomly. Now we submit the big form (the square) and the 4 triangles. The hacker has to derotate the forms, maybe to demirror them, combine them, and submit his solution. It should be NP-hard (I am sorry, I dont know how to proove, I do not know neither for the rest of the puzzles.), should be possible to have a nice flash-game for it, and it should be possible to easy proove the solution. I just dont know how to write a good level-generator. If you are interested, I could help you, but I am not that good in programming.

cu
der Maxist


PS.:
I am really interested in how this post will look like without mistakes, so to speak in normal english. Could someone correct it and pm it to me?

_________________
War is terrorism, but with a higher budget.
Wed Mar 05, 2008 10:48 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
that is an interesting idea, maxist. one thing i wonder, though: has someone already solved this problem? i've seen references to packing problems before, and i wonder if there are known efficient solutions. i want to avoid known problems. but there might be a way to do it that would be different.

thanks,
adum
Thu Mar 06, 2008 4:53 am View user's profile Send private message Visit poster's website
MaxistXXL



Joined: 20 Nov 2007
Posts: 13
Location: Earth

Post Reply with quote
Hi,
the problem which inspired me is unsolvable. It is the question, whether one can tile "the world" with an infinite amount of a given polygon or not. In my pdf they spoke about "the world", I don't know whether they mean a globe or an infinite rectangle. I doubt that there is a good solution for "my" version, but I cannot promise. However, OneOfUs was on the agenda of scientific research already (hamiltonian pathes), and its also on this side.

regards

_________________
War is terrorism, but with a higher budget.
Thu Mar 06, 2008 9:40 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
that is true, that Oneofus is a hamiltonian path problem, and this as been well-studied. however, i don't think there exist any great solutions for hamiltonian paths. oneofus clearly has weaknesses that allow it to be solved pretty easily.

anyway, i think the polygon puzzle sounds interesting... if you want to code up a level generator, that would be nice =)

adum
Thu Mar 06, 2008 9:06 pm View user's profile Send private message Visit poster's website
dk39ab



Joined: 02 Jul 2007
Posts: 4

Post Reply with quote
Actually, if you read up on the literature on Hamiltonian paths and cycles, you'll find that while it is NP-complete in the worst case, it is actually solvable in polynomial time on average for random graphs, at least for some definitions of what a random graph is. My own (current) solver is an only slightly modified implementation of an academically published algorithm.
Mon Mar 24, 2008 9:17 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 391

Post Reply with quote
ah, that's interesting... probably explains all the high scores...
Mon Mar 24, 2008 9:25 pm View user's profile Send private message Visit poster's website
Display posts from previous:    
Reply to topic    hacker.org Forum Index » General Puzzles All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to: 
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 vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.