Lights Out (jeu)

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[4]. 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[4].

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[5]. 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₂, 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₁ et N₂ ci-dessous (représentés sous la forme d’un tableau 5×5, à ne pas confondre avec les matrices).

$${\displaystyle 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₁ et N₂ 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₁, X + N₂, et X + N₁ + N₂, où X est une solution à la configuration de départ. Une introduction à cette méthode a été publiée par Robert Eisele[6].

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[2] - [5] - [7]. 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).

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.

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[7]. 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[8], tandis que les solutions aux tableaux n-par-n quand n≤200 ont été explicitement construites[9].

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[10].