au sommaire
Tetris est un jeu vidéo de puzzle très célèbre, inventé en 1985 par Alexey Pajitnov. En 2002, des informaticiens américains quantifièrent la difficulté du jeu et montrèrent qu’il présente des similitudes avec les problèmes les plus complexes des mathématiques n’ayant pas de solutions simples et nécessitant à la place une analyse exhaustive pour trouver des solutions optimales.
En 2002, des informaticiens américains quantifièrent la difficulté de Tetris. © Suravid, Shutterstock
Principe du jeu Tetris
Dans Tetris, tandis qu’une pièce descend du haut de l’écran, le joueur peut la faire pivoter ou la déplacer latéralement. Les pièces possèdent des formes appelées tétraminos, composées de quatre carrés assemblés de façon à dessiner la lettre L ou un autre motif simple. Quand une pièce atteint un emplacement où elle peut atterrir en bas de l’écran, la pièce suivante amorce sa chute. Chaque fois qu’une ligne du bas de l’écran est totalement remplie, elle disparaît et toutes les lignes supérieures descendent d’une rangée. Le jeu est terminé quand une nouvelle pièce ne peut pas descendre parce que l’écran est totalement rempli. Le but du joueur est de faire durer le jeu le plus longtemps possible afin d’accroître son score.
Le problème NP-complet
En 2002, Erik D. Demaine (né en 1981), Susan Hohenberger (née en 1978) et David Liben-Nowell (né en 1977) recherchèrent une version généralisée du jeu, dont la grille était composée en hauteur et en largeur d’un nombre quelconque de carrés. Ils découvrirent que s’ils essayaient de maximiser le nombre de rangées effacées tout en jouant une suite donnée de pièces, alors le jeu était NP-complet. (NP signifiant « non déterministes polynomiaux »). Cependant, cette classe de problèmes peut être analysée pour déterminer si une solution est correcte, laquelle solution peut réellement nécessiter un temps d’élaboration infiniment long.
L’exemple classique d’un problème NP-complet est le problème du représentant de commerce, dont le but est de déterminer le trajet le plus efficace pour visiter un très grand nombre de villes. La difficulté de ces problèmes provient du fait qu’il n’existe pas de raccourci ou d’algorithme pour une solution rapide.
