Tot vervelens toe buitelen de kleurige blokken van het computerspelletje Tetris voor je ogen over elkaar heen, ook als je de computer hebt uitgezet. De tuimelende blokken laten soms zelfs hun sporen na in je dromen. Het is een uiterst verslavend spelletje, Tetris. En knap frustrerend. Want winnen kun je niet: hooguit je eigen score verbeteren. Tetris werd in 1985 ontwikkeld door de Russische wiskundige Alexey Pajitnov, toentertijd verbonden aan het Instituut voor Computerwetenschappen van de Russische Akademie voor Wetenschappen. Het was het eerste computerspelletje afkomstig van achter het ijzeren gordijn, en het veroverde in korte tijd de rest van de wereld. Het speelbord van Tetris bestaat in de meeste varianten uit een veld van 10 bij 20 vierkantjes. Een voor een dwarrelen de zeven verschillende Tetrisblokken, tetromino’s genaamd, van boven naar beneden over het speelbord. Een tetromino bestaat uit vier vierkantjes die op zeven verschillende manieren gerangschikt kunnen zijn. Er is een vierkante tetromino, een langwerpige, twee L-vormige tetromino’s, twee verschillende trapvormige tetromino’s, en een T-vormige tetromino. Tijdens hun afdaling kunnen de stukken door de speler gedraaid en verschoven worden. Tot ze bij de onderste rij zijn aangekomen, dan liggen ze vast. De bedoeling van het spelletje is om een rij in het speelveld volledig gevuld te krijgen met de tetromino’s. De rij verdwijnt dan uit het speelveld, en de bovenliggende figuren zakken een rij naar beneden om zo bovenin het veld plaats te maken voor nieuwe vormen. Een simpel doch geniaal concept. Gaandeweg het spel vallen de tetromino’s in een steeds hoger tempo, en rest er steeds minder tijd om de vormen in de juiste positie te manoeuvreren. Drie onderzoekers van het Laboratorium voor Computerwetenschap op het MIT in Boston, Erik Demaine, Susan Hohenberger en David Liben-Nowell hebben het spelletje nu grondig geanalyseerd. In een 56 pagina’s tellend artikel concluderen ze: Tetris is moeilijk. Het spelletje blijkt namelijk in een categorie problemen te vallen die wiskundigen NP-problemen noemen. En dat zijn de hardnekkigste breinbrekers van de moderne wiskunde. Een NP-probleem is een probleem waarvan het weliswaar relatief gemakkelijk is om te checken of een gegeven oplossing juist is, maar waarbij oneindig veel tijd nodig is om het probleem als geheel op te lossen. Zoveel tijd, dat het probleem feitelijk als onoplosbaar moet worden beschouwd. Het beroemdste NP-probleem is het handelsreizigerprobleem, waarbij de korste weg tussen een aantal verschillende steden moet worden gevonden. Elke hedendaagse kantoorcomputer heeft tegenwoordig zijn eigen ordinaire NP-probleem: het spelletje mijnenveger, standaard meegeleverd met het besturingssysteem Windows, blijkt ook zo’n NP-hersenkraker te zijn, zo toonde de Britse wiskundige Richard Kaye in het voorjaar van 2000 aan. Erik Demaine en zijn collega’s bestudeerden een sterk versimpelde versie van Tetris, waarbij de speler van te voren precies weet welke tetromino’s in welke volgorde naar beneden komen vallen. In de spelversie is meestal maar een beurt vooruit te kijken. Ook was het in de wetenschappelijke versie mogelijk om de vormen willekeurig vaak te draaien en te verschuiven voor ze op hun plaats vielen. Maar het was zonneklaar: Tetris, zelfs in deze versimpelde vorm, is NP-compleet. De echte variant kan alleen maar nóg moeilijker zijn, concluderen de onderzoekers in het artikel. Om maar niet te spreken van de driedimensionale variant van Tetris, waar schrijver dezes lange tijd in hoge mate aan verslaafd was. Jacqueline de Vree