Extinction des feux

« Lights Out » est un casse-tête logique qui se joue sur une grille composée de lumières, chacune pouvant être allumée ou éteinte. Appuyer sur une lumière quelconque permet de l'allumer ou de l'éteindre, ainsi que toutes ses voisines orthogonales (en haut, en bas, à gauche et à droite). Le but est d'éteindre toutes les lumières. Le casse-tête est trompeusement difficile, car chaque action affecte plusieurs lumières, et en éteindre une peut en allumer d'autres. La version classique utilise une grille de 5x5, mais le concept fonctionne avec n'importe quelle taille de grille.

Règles

1. Le jeu commence avec une grille de lumières, dont certaines sont allumées et d'autres éteintes (ou toutes allumées dans la version classique).
2. Appuyer sur une lumière inverse son état (allumée devient éteinte, éteinte devient allumée).
3. Appuyer sur une lumière fait également basculer toutes les lumières directement adjacentes (en haut, en bas, à gauche, à droite — pas en diagonale).
4. Le but est d'éteindre toutes les lumières.
5. Appuyer deux fois sur la même lumière annule l'opération ; il suffit donc d'appuyer une seule fois sur chaque lumière, voire pas du tout.

Stratégies

• L’ordre n’a pas d’importance : l’état final dépend uniquement des lumières sur lesquelles on a appuyé, et non de l’ordre dans lequel on les a activées. Cela signifie que vous pouvez planifier votre solution sans vous soucier de la séquence.
• Chaque voyant n’est actionné qu’une seule fois au maximum : comme le fait d’appuyer deux fois sur un voyant le ramène (ainsi que ses voisins) à son état d’origine, une solution optimale n’actionne jamais le même voyant plus d’une fois.
• « Chasse aux lumières » (de haut en bas) : Commencez par la ligne du haut. Pour chaque case allumée d’une ligne, appuyez sur la case située directement en dessous pour l’éteindre. Cela « chasse » les lumières vers le bas. Une fois toutes les lignes traitées, seule la ligne du bas peut encore comporter des lumières allumées.
• Correction par bouclage : après la « chasse aux lumières », si la ligne du bas comporte encore des lumières allumées, certains motifs spécifiques de la ligne du haut doivent être inversés avant de recommencer la chasse. Il existe des tables de correspondance connues indiquant quelles pressions sur la ligne du haut corrigent chaque motif de la ligne du bas.
• Approche par l’algèbre linéaire : Le casse-tête peut être modélisé comme un système d’équations linéaires sur GF(2) (le corps à deux éléments, 0 et 1). Chaque pression sur un bouton correspond à un vecteur, et la solution est une combinaison de vecteurs qui produit l’état cible. Toutes les configurations initiales ne sont pas résolubles.
• Motifs neutres : certaines combinaisons d’appuis laissent le plateau inchangé. Comprendre ces « motifs neutres » aide à déterminer si un casse-tête a une solution et à trouver des solutions alternatives.

« Lights Out » a été initialement commercialisé en 1995 par Tiger Electronics sous la forme d’un jeu électronique portable. L’appareil comportait une grille de 5 × 5 boutons rétroéclairés et est devenu un jouet et un casse-tête très populaire. Le jeu proposait aux joueurs des configurations de départ aléatoires et les mettait au défi d’éteindre toutes les lumières.

Cependant, le concept mathématique sous-jacent est antérieur de plusieurs décennies au produit commercial. Le mécanisme de commutation — selon lequel l'actionnement d'un élément affecte ses voisins — a été étudié en mathématiques dès les années 1960 dans le cadre des automates sigma et des automates cellulaires. La théorie mathématique qui sous-tend ce casse-tête fait appel à l'algèbre linéaire sur des corps finis, plus précisément GF(2), où l'addition est équivalente à l'opération XOR.

Ce casse-tête a suscité un vif intérêt chez les mathématiciens et les informaticiens. En 1998, Marlow Anderson et Todd Feil ont publié une analyse mathématique approfondie démontrant qu’exactement 4 des 2^25 (environ 33,5 millions) configurations de départ possibles de la grille 5x5 sont insolubles. Ils ont également démontré que les configurations solvables peuvent toujours être résolues en 15 coups au maximum. L’analyse utilise les valeurs propres de la matrice d’adjacence sur GF(2), établissant ainsi un lien élégant entre le casse-tête, la théorie des graphes et l’algèbre linéaire.

Tiger Electronics a commercialisé une suite intitulée « Lights Out 2000 » avec une grille 6×6, et le concept a été largement adapté dans les jeux vidéo, où il apparaît comme mécanisme de casse-tête dans des jeux d’aventure, des jeux de rôle et des compilations de casse-têtes. Parmi les variantes, on trouve des grilles hexagonales, des grilles toroïdales (en boucle) et des versions comportant plus de deux états d’éclairage. Ce casse-tête reste un incontournable des mathématiques récréatives et est fréquemment utilisé dans les cours universitaires pour illustrer les applications de l’algèbre linéaire.