MazezaM

NP-Hardness

In mathematics, problems (such as puzzle games) can be grouped by their complexity. Roughly speaking, this is a measure of the time it takes an optimal algorithm to solve them. It is useful to know if a problem is NP-hard, since it tells us that there is no known efficient algorithm for solving it. A friend of mine, Ben North, has produced an extremely elegant argument that MazezaM is NP-hard. Ben establishes NP-hardness by encoding 3-SAT problems as MazezaM levels, such that that the level is solvable if and only if the 3-SAT problem is. Since the encoding can be done efficiently, any efficient algorithm which solved MazezaM could be used to efficiently solve the 3-SAT problem. Thus, MazezaM must be at least as difficult as 3-SAT.

Thanks to Aaron Williams who contacted Ben and I to point out that while Ben had proved that MazezaM is NP-hard, the original claim that it was NP-complete was not correct.

Prior Art

With the original release of MazezaM in 2002, I included a MazezaM.txt file which stated:

"To the best of my knowledge MazezaM's specific game logic is original. Unfortunately, there are so many puzzles out there that it is impossible for me to be sure. If you are aware of a prior instance of the idea, please get in touch.""

Well, 17 years later, I was finally informed of such a prior instance. (Thanks Aaron!) It turns out that there is very similar game, and it actually preceeds MazezaM by a few years: Storm Seas by Binary Arts (a.k.a. Wave Breaker by ThinkFun). In this case, it's not a video game, but a mechanical puzzle. The rules differ slightly, but both games are fundamentally about moving an avatar around a maze of sliding rows.

As I stated with the original release, my inspiration for MazezaM was a recollection of the games Fall Guy (from the book "Sixty Programs for the Oric-1") and Sokoban.