Tetris is NP-Volledig

R. Breukelaar, E.D. Demaine, S. Hohenberger, H.J. Hoogeboom, W.A. Kosters, D. Liben-Nowell. Tetris is Hard, Even to Approximate. Special Issue: Selected Papers from the Ninth International Computing and Combinatorics Conference (COCOON 2003), Big Sky, MT, USA, July 2003. International Journal of Computational Geometry and Applications 14 (2004) 41-68. doi:10.1142/S0218195904001354
De Wetenschap van Tetris,
Leidsche Flesch lunch lezing (pdf)

Tetris (nl.wikipedia)

250 of the most intriguing mathematical milestones including: … The Mobius Strip (1858) • Riemann Hypothesis (1859) • Flatland (1884) • Proof of the Prime Number Theorem (1896) • Hairy Ball Theorem (1912) • Infinite Monkey Theorem (1913) • Geodesic Dome (1922) • Bourbaki: Secret Society (1935) • Chaos and the Butterfly Effect (1963) • Fuzzy Logic (1965) • Rubik's Cube (1974) • Fractals (1975) • The On-Line Encyclopedia of Integer Sequences (1996) • Tetris Is NP-Complete (2002) • Checkers Is Solved (2007) • Mathematical Universe Hypothesis (2007)

Het oorspronkelijke bewijs van Demaine, Hohenberger and Liben-Nowell, kon op basis van een idee van Ron Breukelaar een stuk getroomlijnd worden. De NP-volledigheid van Tetris is één van de mijlpalen uit

Het WiskundeBoek

Clifford A. Pickover, Librero (Mathbook, Sterling Publishing)

In 2002 hebben Amerikaanse computerwetenschappers de moeilijkheidsgraad van Tetris vastgesteld en aangetoond dat het overeenkomsten heeft met de moeilijkste wiskundeproblemen: een optimale oplossing vergt een uitputtende analyse.

Ivars Peterson, see MathTrek "Tetris Is Hard," The Mathematical Association of America, October 28, 2002.

Tetris is Onbeslisbaar

Als we de regels een beetje buigen is Tetris zelfs onbeslisbaar. Gegeven een beschrijving van hoe de stukken kunnen gaan vallen (als reguliere taal) bestaat er geen algoritme dat bepaalt of een van de mogelijkheden het bord leeg achter laat.

H.J. Hoogeboom, W.A. Kosters. Tetris and Decidability. Information Processing Letters 89 (2004) 267-272. doi:10.1016/j.ipl.2003.12.006

Tetris Plaatjes

Elk patroon kan gemaakt worden door de juiste stukjes te laten vallen. Dat hebben we in deze paper laten zien. Elk patroon? Bijna, volle en rege legels kunnen niet, en als de breedte van het veld een viervoud is moet het aantal blokjes dat ook zijn natuurlijk.

H.J. Hoogeboom, W.A. Kosters. How to Construct Tetris Configurations. International Journal of Intelligent Games and Simulation 3 (2004) 94-102.

Applet: ontwerp en plaatje en zie hoe het ontstaat door vallende Tetris vormpjes. (Walter Kosters)