Sunday, May 2, 2010

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

1 comment:

  1. Mapping (in polytime) the boolean satisfiability problem (SAT) onto a level in the game prove that the game is NP-hard. Did you prove that it is in NP, too? (i.e. every solvable Push Down level has a solution which size is polynomial in respect to the size of the level)

    ReplyDelete