Author 
Message 
adum
Joined: 19 Apr 2007 Posts: 392


Puzzle Suggestions 

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 subsecond time
Let us know your thoughts!
adum


Fri May 11, 2007 10:57 pm 


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



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 


adum
Joined: 19 Apr 2007 Posts: 392




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 NPhard, 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 nphard 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 


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





sokoban has been proven NPhard, by the way.

A little stronger: it's complete for PSPACE.


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

To state the obvious: a good puzzle should probably be NPhard. 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 


adum
Joined: 19 Apr 2007 Posts: 392






A little stronger: it's complete for PSPACE. 
i don't really know the difference =/ should do some reading...


To state the obvious: a good puzzle should probably be NPhard. 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.


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 


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







A little stronger: it's complete for PSPACE. 
i don't really know the difference =/ should do some reading...

Obligatory excessdetail:
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.


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 


JamesCFraser
Joined: 06 Jun 2007 Posts: 5




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


* : 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
________
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 


adum
Joined: 19 Apr 2007 Posts: 392




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 levelgenerating algo, let me know  maybe we can use it.
cheers,
adum


Mon Jul 09, 2007 3:20 am 


JamesCFraser
Joined: 06 Jun 2007 Posts: 5




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 


MaxistXXL
Joined: 20 Nov 2007 Posts: 13 Location: Earth 



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 NPhard (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 flashgame for it, and it should be possible to easy proove the solution. I just dont know how to write a good levelgenerator. 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 


adum
Joined: 19 Apr 2007 Posts: 392




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 


MaxistXXL
Joined: 20 Nov 2007 Posts: 13 Location: Earth 



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 


adum
Joined: 19 Apr 2007 Posts: 392




that is true, that Oneofus is a hamiltonian path problem, and this as been wellstudied. 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 


dk39ab
Joined: 02 Jul 2007 Posts: 4




Actually, if you read up on the literature on Hamiltonian paths and cycles, you'll find that while it is NPcomplete 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 


adum
Joined: 19 Apr 2007 Posts: 392




ah, that's interesting... probably explains all the high scores...


Mon Mar 24, 2008 9:25 pm 




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


