# MazezaM - Puzzle Game

Version 2.0 of MazezaM is now complete, located here! The game now includes saving, a level select screen, an in-level menu, and the controls have changed slightly. Undo is now mapped to the A button and the menu is accessed with the B button.

1 Like

You should probably get @ardubeast to edit that into the main post as well.

1 Like

Version 2.5 is now available, the download link can be found in the original post. In addition to some menu changes, this version allows you to save your progress midway through a level to come back to later, and includes an extra level at the end.

2 Likes

I’ve been playing with this updated version for about a week now and it is very enjoyable. The save feature tracks which levels you have completed (and with how many moves you made on each), and you can also save your intermediate progress on one level. This has encouraged me to work through to some of the higher levels for the first time. As @jay mentioned the button functions have now been ironed out as well. Overall, this is probably my new favorite version of MazezaM. Congratulations Aster!

1 Like

re: extra level. The level that @jay mentioned is based on a new academic paper on MazezaM which will be presented at a conference in Japan in late-August. Despite the compact 128x64 resolution of the Arduboy, this new level alone takes over 200 moves to solve.

More generally, the paper shows that MazezaM levels can take an exponential number of moves to solve with respect to the size of the level. This property is shared by other notoriously difficult puzzle games like Sokoban and Rush Hour and maybe @crait’s Circuit Dude has this property too?

For those who are interested, the levels in the paper can only be solved by following a specific pattern known as the binary reflected Gray code and a larger level is shown below. MazezaM was previously shown to be NP-hard, and the new result is one reason to believe that it could be PSPACE-hard. The paper was written with the original creator of MazezaM (Malcolm Tyrrell), the author of the NP-hardness result (Ben North), a student from MIT (Justin Kopinsky), and with @jay from Bard College at Simon’s Rock contributing to the work this summer.

3 Likes

I’d love to pretend I understood it all, but I never get on well with formal academic papers. (I find they tend to be formal to the point of obfuscating the explanation (and yes, I see the irony in that), or quite maths-heavy.)

I sort of get the idea of it at least, even if not through the RBC approach.
From the image alone I can see how that level is composed of the same pattern repeated many times, and that each time you extend the pattern you exponentially increase the number of moves required to solve the level (thanks to required back-tracking).

Also I can see the relation to sokoban.
In sokoban the player can move in 2 dimensions and boxes can move in 2 dimensions, whereas in mazezam the rules are similar but the player moves in 2 dimensions and ‘boxes’ only move in 1 dimension.

Wait a minute, why does this link to my comment in particular?

Did I accidentally suggest something that might suggest Circuit Dude is NP-Complete?
Or do you just want the world to buy a pigeon dating-sim? (I regret nothing!)

It well might be though.
A lot of these sorts of puzzle games have similarities to the travelling salesman problem in that they consist of a sequence of choices (in particular, which direction to travel in at any given point) and have a well defined start and end point.