MazezaM is NP complete

Update 20170129: My claim that Mazezam is NP-complete is not shown by this argument. The argument does show that Mazezam is NP-hard, but it is not clear that Mazezam is itself in NP. See a follow-up post for more details. Many thanks to Aaron Williams for contacting me to point out my error.

The post about AutoFickle reminded me of something I did a good while ago (2008) which doesn’t currently have a home. The connection is that this is also a project based on a game written by Malcolm Tyrrell. The game this time is MazezaM, dated 2002–2004; in it you push rows of blocks back and forth, trying to get from the entrance to the exit of a maze. It’s a nice game.

It seemed like the sort of thing which ought to be NP-complete, in the same way that other puzzle games have turned out to be. (See, e.g., David Eppstein’s page ‘Computational Complexity of Games and Puzzles’ for a thorough survey.) I think I managed to demonstrate that MazezaM is, indeed, NP-complete.

The argument is sketched in this PDF. The conclusion is that you can construct a MazezaM level like

to represent an instance of the Boolean satisfiability problem (3-SAT), where solving the MazezaM level is equivalent to finding an assignment of the variables in the 3-SAT instance.