Lumines is NP-complete : Or at least if your gamepad is broken

Abstract: Lumines is a popular puzzle game where the player organizes dichromatic 2 × 2 blocks on a rectangular grid by rotating and moving them around the gameboard. A line eventually sweeps the gameboard and clears all 2 × 2 monochromatic squares that the player has formed. This report examines the complexity of offline Lumines with two significant simplifications: squares are cleared instantly when formed and the player is not allowed to rotate the blocks. A decision problem is formulated for this model and shown to be in NP. The NP-complete subset sum problem is reduced to the decision problem, thereby proving the Lumines model to be NP-complete. The essence of the reduction from subset sum shows potential for further use in similiar stacking 2-dimensional puzzle games.