Lumines is NP-complete: Or at least if your gamepad is broken
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
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.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-168182OAI: oai:DiVA.org:kth-168182DiVA: diva2:814621