Escape: Most recent comments

Browsing all comments (spoilers: on | off) (info: on | off)

Satisfiability

Wed 15 Sep 2004 09:06

<Tom 7> Cool! Yes, this would show that it's NP-hard. To show that it's NP-complete, you'd need to show that it's also in NP. That would mean that we could verify that a level has a solution in time polynomial to its size, once given a solution. It is certainly polynomial to verify a polynomial-size solution, but it is not obvious to me that every solvable level has a polynomial-size solution. (ie, some levels may be VERY HARD in the sense that they require an exponential number of moves.) Since Escape embeds several other games such as Sokoban and (sort of) the UFO puzzle, there may already exist some results that imply it is harder than NP (unfortunately the other direction would probably have to be a new theorem).
<mjn> I think the "determine if an Escape level has a solution" problem is NP-complete: here's one way to reduce an instance of SAT to an Escape level.
Each row of stop signs is a variable, and the gadgets on the left let you assign "true" or "false" by sending you through a chain of teleports. This level is (A or B) and (not A or B or C) and (not B or not C).

Been a while since theory class--is there something to be proved in the other direction, too?

Memory Hole

Mon 13 Sep 2004 23:10

<Tom 7> Great title. =) Nice one!

Jungle Fever

Wed 08 Sep 2004 17:09

<Tom 7> This level is really hard! I haven't gotten it yet...

Impossible

Fri 03 Sep 2004 23:42

<rjmccall> Argh, you.

Worried

Tue 31 Aug 2004 21:05

<Tom 7> Testing again. I think this is the earliest example of a "draw a picture" Escape level.

Fri 27 Aug 2004 13:50

<Tom 7> Just debugging comments... sorry.

Escape Vomit

Thu 26 Aug 2004 00:03

<Max> Yeah, I actually spent a good deal of time trying to make this look as nauseating as possible...
<Tom 7> Nnnnnnghhhhhh....

There's got to be a way!

Tue 24 Aug 2004 12:25

<rjmccall> There is one point in this level where logical inferences play an important role in saving players time. Everything else is brute-force search. Argh.

Impossible

Tue 17 Aug 2004 22:12

<Tom 7> Right now I'm ready to believe it's impossible. ;)

Start at the End

Tue 17 Aug 2004 00:13

<Max> Yeah, this one's really easy. I just dashed it off to kill a few minutes. Finish yours cause it'll probably be a lot more interesting!

Claustrophobia II

Tue 17 Aug 2004 00:11

<Max> Yeah, inspired by levels like "Bullseye" and "Specific Gravity" I wanted to see what the minimum amount of tiles necessary for a level to remain somewhat challenging. I think this one gets kind of close, at least!

Breaking In

Tue 17 Aug 2004 00:08

<Max> It took me a while to get it, too ;)
<Tom 7> Whoopee! Got it.
<Tom 7> This one is beautiful. I love simple symmetric ones. I'm still stuck, though...

Claustrophobia II

Mon 16 Aug 2004 23:09

<Tom 7> I think this is superior in its tininess to, say, Bullseye. But like that one, my solution came from random movement, not from careful planning. That's too bad...

Start at the End

Mon 16 Aug 2004 23:06

<Tom 7> I was working on a level with a similar theme!
There's a lot of space to move around in this one, so the traps don't present much of a challenge...

Phospholipid Bilayer

Sun 15 Aug 2004 00:47