« back             Browsing Levels: #378 "Gangnails!"
prev: #377 "108% Fat Free" next: #379 "Laser Democracy in the Heartland"

"Gangnails!" by Brian Potetz (with some help from the ancients)

added 26 Feb 2005 17:14
Shortest Solution
NameSpeed Record
Length524 moves
On30 Mar 2005 10:47

Comments (turn spoilers off)
988 Gangnails! Doom (371) Wed 30 Mar 2005 10:47 SPOILER
  Added speedrun: 524 moves (old: 999999).
450 Gangnails! Max (61) Mon 28 Feb 2005 00:07  
  Hey, this is pretty neat. I got a nice "surprise" at the end, too!
440 Gangnails! Tom 7 (1) Sun 27 Feb 2005 11:31  
  Cool, thanks! This is very simple, huh...

So know it is known that:
(1) Escape solvability is NP-hard (Several embeddings, or (2))
(2) Escape solvability is PSPACE-hard (Sokoban reduction + Sokoban PSPACE-completeness)
(3) Escape solvability is probably not in NP, unless there is some method for short-cutting the discovery of exponential solutions like this.
(4) Escape solvability should be in NPSPACE (no need to save the solution as you go, and the game only needs poly space (actually constant!) to execute moves), which means that it is in PSPACE since PSPACE=NPSPACE.
(5) Escape is PSPACE-complete (2, 4) and not NP-complete unless NP=PSPACE.

(I am not an expert on this stuff!)
439 Gangnails! bpotetz (144) Sat 26 Feb 2005 17:17 SPOILER
  This is actually the second escape level I ever wrote. But I never uploaded it because I thought it was too boring in this form. But last night, Tom said he was looking for a level to show that solving escape was super-polynomial. In exchange for this proof, he said he would play all my escape levels. So here it is - the Chinese Puzzle Rings, aka the Devil's Needle, aka Cardan's Rings, aka Meleda, aka Gangnails.