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

« 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

Solved 59/59

Cooked 0/59

Difficulty 2.10

Style 5.18

Rigidity 7.25

Shortest Solution
Name Speed Record

Length 524 moves

By Doom

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

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.