# Lights Out (jeu)

Lights Out est un jeu électronique commercialisé par Tiger Electronics en 1995. Le jeu est composé d’une grille de cinq par cinq lumières. Quand le jeu commence, un nombre aléatoire ou un motif enregistré de ces lumières s’allument. Appuyer sur l’une des lumières basculera la position des lumières adjacentes à celle-ci. Le but du jeu est d’éteindre toutes les lumières, de préférence avec le moins de coups possible$^,$.
Merlin, un jeu électronique similaire, a été commercialisé par Parker Brothers dans les années 1970 avec des règles similaires, mais sur une grille de trois lumières par trois. Un autre jeu de ce genre a été produit, par Vulcan Electronics, en 1983, sous le nom de XL-25. Tiger commercialisa également une version cartouche de Lights Out pour leur console portable Game.com, le jeu étant alors fourni avec la console.
Un certain nombre de jeux dérivés de Lights Out ont par la suite vu le jour, tels que Lights Out 2000 (5×5 avec différentes couleurs), Lights Out Cube (six faces en 3×3 avec des effets au niveau des arrêtés), et Lights Out Deluxe (6×6).

## Inventeurs

Lights Out a été créé par un groupe de personnes comprenant Avi Olti, Gyora Benedek, Zvi Herman, Revital Bloomberg, Avi Weiner et Michael Ganor. Les membres de ce groupe ont, seuls ou ensemble, également inventé plusieurs autres jeux, comme Hidato, NimX, iTop et bien d’autres encore.

## Système de jeu

Le jeu est composé d’une grille de cinq par cinq lumières. Quand le jeu commence, un nombre aléatoire ou un motif enregistré de ces lumières s’allument. Appuyer sur l’une des lumières basculera la position des lumières adjacentes à celle-ci. Le but du jeu est d’éteindre toutes les lumières, de préférence avec le moins de coups possible.

### Mathématiques

Si une lumière est allumée, elle doit être pressée un nombre impair de fois pour être éteinte. Si une lumière est éteinte, il faut la faire presser un nombre pair de fois (0 compris) pour qu’elle reste éteinte. Plusieurs conclusions sont utilisées pour la stratégie du jeu. Premièrement, l’ordre dans lequel on appuie sur les lumières n’a pas d’importance, car le résultat sera le même. Deuxièmement, dans une solution optimale (nombre minimum de coups), chaque lumière ne doit pas être pressée plus d’une fois, car appuyer deux fois sur une lumière équivaut à ne pas appuyer dessus du tout.
En 1998, Marlow Anderson et Todd Feil ont utilisé l’algèbre linéaire pour prouver que toutes les configurations ne sont pas solvables, et également qu’il existe exactement quatre scénarios gagnant, sans compter les coups redondants, pour tout problème en 5×5 solvable. La grille en 5×5 de Lights Out peut être représentées comme un vecteur colonne 25x1 où un 1 et un 0 signifient respectivement qu’une lumière est allumée ou éteinte. Chaque entrée est un élément de Z$_2$, le champ des entiers modulo 2. Anderson et Feil ont découvert que pour qu’une configuration puisse être résolue (en dérivant le vecteur nul de la configuration originale), elle doit être orthogonale aux deux vecteurs N$_1$ et N$_2$ ci-dessous (représentés sous la forme d’un tableau 5×5, à ne pas confondre avec les matrices).
$N_{1}={\begin{pmatrix}0&1&1&1&0\\1&0&1&0&1\\1&1&0&1&1\\1&0&1&0&1\\0&1&1&1&0\end{pmatrix}},N_{2}={\begin{pmatrix}1&0&1&0&1\\1&0&1&0&1\\0&0&0&0&0\\1&0&1&0&1\\1&0&1&0&1\end{pmatrix}}$
En outre, ils ont découvert que N$_1$ et N$_2$ peuvent être utilisés pour trouver trois solutions supplémentaires à une solution et que ces quatre solutions sont les quatre seules solutions (sans compter les mouvements redondants) à la configuration de départ donnée. Ces quatre solutions sont X, X + N$_1$, X + N$_2$, et X + N$_1$ + N$_2$, où X est une solution à la configuration de départ. Une introduction à cette méthode a été publiée par Robert Eisele.

### Chasse à la lumière

La « chasse à la lumière » est une méthode similaire à l’élimination gaussienne qui permet de toujours résoudre l’énigme (si une solution existe), mais avec la possibilité de nombreuses étapes redondantes$^,$$^,$. Dans cette approche, les rangées sont manipulées une par une en commençant par la rangée supérieure. Toutes les lumières sont éteintes dans la rangée en changeant l’état des lumières adjacentes dans la rangée directement en dessous. La même méthode est ensuite utilisée sur les rangées consécutives jusqu’à la dernière. La dernière rangée est résolue séparément, en fonction de ses lumières allumées. Les lumières correspondantes (voir le tableau ci-dessous) de la rangée supérieure sont changées et l’algorithme initial est exécuté à nouveau, ce qui donne une solution (très peu souvent optimale).
| Ligne inférieure | Ligne supérieure |
Les tableaux et les stratégies pour d’autres tailles de tableau sont générés en jouant à Lights Out avec un tableau vierge et en observant le résultat de l’apport d’une lumière particulière de la rangée supérieure vers la rangée inférieure.

### Résultats supplémentaires

Lorsqu’une des solutions possibles est trouvée, une solution avec le nombre minimum de coups peut être déterminée en éliminant les coups « redondants », inutiles, n’ayant pas d’effet cumulatif. Si le puzzle ne peut être résolu dans le cadre légal du jeu, les deux lumières du bas les plus à gauche resteront allumées quand toutes les autres lumières auront été éteintes.
L’existence de solutions a été mise en évidence pour une large sélection de configurations initiales, comme l’hexagone, tandis que les solutions aux tableaux n-par-n quand n≤200 ont été explicitement construites.
Il existe une solution pour tout tableau en N×N. Il est soluble sur n’importe quel graphe non orienté, où cliquer sur un sommet retourne sa valeur et ses voisins. Plus généralement, si la matrice d’action est symétrique, sa diagonale est toujours résoluble.

## Modes de jeu

La version originale du jeu propose, fait étonnant pour l’époque sur un tel jeu, un éditeur de niveau.
Après l’avoir commercialisé sous forme de jeu électronique en 1995, Tiger Electronics proposa à la vente sa Game.com, fournie avec son best-seller du moment, le fameux Lights Out. Cette version cartouche du jeu de réflexion présente quelques ajouts par rapport à l’originale. Il est tout d’abord à noter que la grille est alors en 6x6, et non plus en 5x5. Deux nouveaux modes de jeu, avec de nouvelles contraintes, font leur apparition : Lit Only, où le joueur ne peut changer l’état que des lumières allumées, et Toggle, où le joueur doit alterner entre lumières allumées puis éteintes, et ainsi de suite. À noter que ces trois modes (les deux nouveaux et l’original) sont disponibles en version aléatoire, offrant ainsi pour chacun d’eux un panel de plus de 60 milliards de possibilités de configuration des lumières.

## Ventes

Les chiffres de ventes de la version originale du jeu sont encore à ce jour inconnus, mais les recettes générées ayant notamment permis le financement de la conception et de la commercialisation de la Game.com, il est possible de penser que le jeu électronique se vendit de manière satisfaisante.
La version cartouche sur Game.com étant fournie avec la console durant la totalité de la commercialisation de la console, les chiffres de vente de la Game.com et de cette version de Lights Out peuvent être confondus. Ces chiffres sont estimés à environ 300 000.