Sokoban-style PushPush Games with Unique Solutions

Based on the 1994 Macintosh computer game of the same name, the PushPush variation on Sokoban, which we refer to as PushPush-Storage, is a block pushing puzzle in which the player controls an agent on an integer lattice populated with blocks, where pushing a block causes it to slide to the maximum possible extent without momentum transfer to other blocks, and where the objective is to cover a fixed set of storage sites with unmoving blocks. Here, we consider the problem of designing non-trivial instances of PushPush-Storage puzzles where one can easily quantify how close the player is to finding a given solution. Towards this objective, we show that randomized polynomial time reductions from Boolean satisfiability problems can be used to efficiently construct PushPush-Storage puzzles having unique solutions while also not admitting polynomial time algorithms unless NP =RP. Accordingly, provided a game designer can find a solvable PushPush-Storage puzzle and its solution, the uniqueness of its solution provides a direct means of both quantifying the percentage completion of the puzzle and of determining if a player has become trapped. Finally, we establish that PushPush-Storage puzzles are hard for Ueda and Nagao's class of Another Solution Problem (ASP) function problems.