Push Down! is NP-Complete

A friend of mine (nick: diophant) has proven that my android game Push Down! is NP-complete. The proof is surprisingly simple and he did it by showing how the boolean satisfiability problem (SAT) can be mapped onto a level in the game. Instead of a formal proof here is an example:

The equation is:

(A v B v C) (-B v -C) (-A v B) (-B v C)

and the corresponding level is here:

Each literal in the equation is a color in the map (A = green, B = blue, C = yellow). Due to the linked-block property of the game, same colored blocks can only move together. The three blocks on the left are the switches to set each literal to a value of either 0 or 1. Currently they are all set to 0 and moving them up would set them to 1. The four columns on the right are for each term in the equation. If you can find an assignment of A, B and C so that the equation evaluates to TRUE you can find a way to the exit otherwise not.

With this construction it is easy to see that you now can build a map for any given boolean equation but they would quickly grow in size and would be rather confusing to solve. Nevertheless this shows that Push Down! is indeed NP-complete.

If this was a little confusing here is some more detail. The equation above means 

(A or B or C) and (not(B) or not(C)) and (not(A) or B) and (not(B) or C).

The first column is currently blocked completely (A, B, and C are 0) but it is enough to flip one of the literals to make a way and also make the first term in the equation evaluate to TRUE. For example let us flip C (yellow) by moving it up. Now the first term evaluates to true and actually the whole equation evaluates to true as we now can walk the the end of the maps on the right.

If you have any questions or comments write them down below in the comments.

Push Down! Game Page

Push Down! Update to v1.1.0

A new update for Push Down is released. I added a new challenge mode with 14 new maps. These maps can be played individually and in any order. On successful completion you get some fruit. More information can be found at the official website www.mystictri.com.

Push Down! Lite

I just finished and released Push Down! Lite to the android market. It is the free version of my game Push Down! and comes with 7 levels. Below you find the QR-Code that takes you directly to the download with your phone:

Push Down! Small Update to v1.0.1

Just released a small update for Push Down! for Android. I changed the way how the ghost is controlled. You now have the choice between three different control schemes. The new and now default setting is via gesture control (slide along the screen for movement). Type A is the old control scheme and Type B is similar but with the arrows for left/right movement moved to the right of the screen to be controlled by your right hand. Let me know what you think about the new control schemes.

Push Down! Released on Android Market

A few minutes ago I released Push Down! on the Android Market.  Here are two screenshots for you.

The official description is:

A small ghost has lost his soul, but he wants it back. Help him by solving 42 levels and by uncovering the secret of the linked blocks. Find your way to the stairs that lead down and collect keys to open up new passages.

The features include:

•  Undo a wrong move
•  Replay any level you have solved
•  Try to find a solution with the minimum number of steps

Welcome

Welcome to the MysticTri blog. Here you will find news and progress reports about my mobile game developments.
Currently I am in the final testing phase of a new Android game called Push Down! As a teaser you can see the main character on the left. It is a puzzle game about a small ghost who has lost his soul and who wants to find it again. The only thing that is missing before I can release it to the Android market place is some fine tuning on the levels to make sure they are all fun and neither too easy nor too difficult.