Puzzle Suggestions

[adum]

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

[ShardFire]

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'.

[adum]

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

[Captain Segfault]

sokoban has been proven NP-hard, 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 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...

[adum]

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 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.

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

[Captain Segfault]

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.

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!

[JamesCFraser]

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: Select all

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

[adum]

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

[JamesCFraser]

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

[MaxistXXL]

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?

[adum]

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

[MaxistXXL]

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

[adum]

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

[dk39ab]

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.

[adum]

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