Sitting down with a bunch of old games in the Super Mario Bros., Donkey Kong, Legend of Zelda, Pokemon and Metroid franchises, Belgian scientists have proven beyond all doubt that those games are way hard. To showcase their work, they've written a scientific paper outlining their findings.
Greg Aloupis, Erik D. Demaine and Alan Guo, from the Free University of Brussels, ultimately found that most of the games can be classified as "NP-hard", a scientific term meaning they're about as tough as a problem can get.
While you'd think this is all a joke, and it mostly is, reading the paper shows a lot of thought has gone into it. Serious thought. Here's Pokemon, for example:
The no-reverse gadget serves a similar function as the one-way gadget, except after traversing from a to b, the player cannot traverse it from b to a. This is implemented by the gadget in Figure 21. Clearly, the player cannot enter via b, because that lures the weak Trainer to block the passage. Suppose the player enters through a. They can safely walk to b, because the weak Trainer is blocking the bottom strong Trainer's line of sight. However, to reach b, the player must lure the weak Trainer out of the line of sight of the strong Trainer, hence the player may never return in
the reverse direction.
And here's the sliding block puzzles from Zelda:
Generalized Legend of Zelda is NP-hard by reduction from a puzzle similar to Push-1, because Legend of Zelda contains blocks which may be pushed according to the same rules as in Push-1 [2], except that in Zelda, each block may be pushed at most once. Fortunately, all of the gadgets in the reduction for Push-1 found in [2] still function as intended when each block can be pushed at most once, with the possible exception of the Lock gadget. However, a simple modication to the Lock gadget (illustrated in Figure 11) suces. (Here we assume that Link has no items, in particular, no raft.)
more at kotaku.comhttp://kotaku.com/5892690/science-proves-old-video-games-were-super-hard
