MazezaM

Contents

MazezaM: a puzzle game which I invented.

The MazezaM Engine: an application in which MazezaM and several other puzzles can be played.

mzmsolve: a program which solves mazezam levels.

NP-Completeness: a result (due to Ben North) proving that MazezaM belongs to a class of difficult problems.

Downloads: software for MazezaM.

MazezaM

MazezaM is a simple puzzle game which I invented in 2002. Its name is pronounced "may-zam".

The rules are very simple: The goal is to get the character from the left of the mazezam to right. You may slide the rows of blocks left and right by pushing them. For more details, read MazezaM.txt.

A number of implementations currently exist:

• The MazezaM Engine, which runs on most modern computer systems. See below.
• The original version, from 2002, for the ZX Spectrum.
• Several versions by Ventzislav Tzvetkov for various older platforms, including the Gameboy, C=64, Oric Atmos and Apple][. He has produced an excellent version for the Amiga which features animated graphics and music.
• A plug-in for Rockbox (software for digital audio players).

All implementations are free software.

The MazezaM Engine

The MazezaM Engine is a puzzle application, which supports MazezaM and several Sokoban variants. Specifically, it supports MazezaM, Sokoban, Hexoban, Trioban, Multiban and Octoban (my own Sokoban variant).

As well as being a stand-alone application, the MazezaM Engine is also designed to work as an applet which runs inside your browser. If your browser has a recent version of Java, then you can play MazezaM now.

The MazezaM Engine is free software. Among other things, this means that the source is available for you to use or improve. Note: The MazezaM Engine is a personal project, so the code was not intended to be accessible.

A note on the design of the MazezaM Engine

The MazezaM Engine started life as a simple applet. I soon found myself wondering if I couldn't generalise the code to support other game types. Ultimately, this lead to several kinds of generalisation:

Level contents

Levels are constructed out of a hierarchy of components which may be collections of sub-components, components with holes, etc. A move is possible if the resistance to moving all effected components (determined recursively) is less than the player's strength.

Tessellation

Levels are independent of the tessellation (i.e. grid pattern). Thus, the only difference in the code between Sokoban, Hexoban, Trioban and Octoban is parsing and construction.

Rules

Levels determine their own criteria for completion.

Graphics

There are no dependencies on bitmaps or fixed pixel sizes. Level components are drawn by tracing outlines. A nice consequence is that levels can scale to the fit the window.

So is the gain in generality worth the resulting complexity? Probably not!

mzmsolve

A program which solves MazezaM levels. Using it, I've obtained optimal solutions to the original ten levels. (Solutions are written as a sequence of direction letters, which are capitalized if the direction corresponds to a push.)

The program can find three different types of solution:

Any solution

Uses a depth-first algorithm to find a solution as quickly as possible.

Move-optimal

Uses a breadth-first algorithm to find a solution with the fewest moves. This is slowest.

Push-optimal

Uses a breadth-first algorithm to find a solution with the fewest pushes. This is faster than finding move-optimal solutions. Note: the solution produced is not guaranteed to be a solution with the fewest moves of those which have the fewest pushes.

New: I've included an implementation of the A* search algorithm. For levels of human-solvable size, this is slower than the above searches, so it is not the default. For finding move-optimal solutions, it should handle large levels better than the defaults. Unfortunately, I have yet to find a good heuristic for guiding push-optimal searches, so don't expect it to work well in that case.

You can download the source code to mzmsolve below.

NP-Completeness

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. An important class of problems are the NP-complete problems. Inefficient algorithms which solve these are known, but it is still unknown whether efficient argorithms exist (this is the famous P=NP question.)

During a discussion about implementing the A* algorithm, I introduced MazezaM to a friend, Ben North. Shortly thereafter, he produced an extremely elegant argument that MazezaM is NP-complete (pdf).

To show a problem is NP-complete, one typically shows that (a) it is in the class NP and (b) that it is at least as difficult to solve as another problem known to be NP-complete. (a) is obvious for MazezaM. Ben establishes (b) 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.

Downloads

• MazezaM-1.2-beta.zip --- the most recent release
• Note: a recent version of the Java Runtime Environment is required (at least JRE 6)
• levels.xml --- A file containing levels for all supported games
• MazezaM-1.2-beta-src.zip --- its source code
• mzmsolve-1.1 --- the C++ source code to mzmsolve.
  • Requires a C++ compiler, make and an implementation of getopt.
  • The code is richly annotated using Doxygen comments.
• ZXMazezaM.zip --- the ZX Spectrum version of MazezaM. You'll need an emulator.
  • ZXMazezaM_src.zip --- the ZX Spectrum Basic source code for ZXMazezaM.
  • Note: The build process uses zmakebas, python, cpp and (optionally) make.