Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Lumines is NP-complete: Or at least if your gamepad is broken
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-168182OAI: oai:DiVA.org:kth-168182DiVA: diva2:814621
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-27 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

fulltext(535 kB)139 downloads
File information
File name FULLTEXT01.pdfFile size 535 kBChecksum SHA-512
f3daab04e53536d18d6bc180a279f408ee1eb03e16235b42e9324728cfeeb63e062ca6ba5b97899baea3bcf3e5ed6d9889268d066a9e3904c99bdcdc99437365
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 139 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 202 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf