Solveur Lights Out

Lights Out (ou Flip Tiles game) est un jeu électronique composé d'une grille de cases lumineuses (parfois avec des ampoules) ou numérotées (originellement de 5x5) qui consiste à éteindre toutes les lumières d'une grille.

Au début du jeu, un motif de cases est allumé (différents états). En appuyant sur l'une des cases, elle agit comme un interrupteur, elle bascule d'état (elle passe d'allumée à éteinte, ou change d'éteinte à allumée ou modifie sa couleur), ainsi que les quatre cases adjacentes (voisines haut, droite, bas et gauche).

Le but du jeu est de basculer toutes les lumières en position éteinte (ou allumée), de préférence en appuyant sur le moins de cases possibles.

Le joueur doit réfléchir sur quelles cases il doit appuyer pour éteindre toutes les lumières.

Un clic sur la case du milieu donne le résultat suivant :

(la case cliquée ainsi que les 4 cellules adjacentes (haut, bas, droite, gauche) ont changé d'état)

Pour un jeu à $ n $ états, appuyer sur une case $ n $ fois la remet à son état initial.

Il existe plusieurs variantes et options dans Lights Out :

— Taille de la grille : différents format de grille sont possibles, allant de 3x3, 4x4, 5x5, 6x6 à des tailles plus grandes voire rectangulaires.

— État de départ aléatoire ou défini : les lumières peuvent démarrer dans des configurations diverses.

— Actions limitées : le nombre de changements d'état autorisé peut être restreint pour augmenter la difficulté.

— Jeu chronométré : un compte à rebours peut ajouter un défi supplémentaire pour terminer le jeu dans un délai imparti.

— Obstacles : certaines variantes introduisent des cases noires qui ne peuvent pas être changées d'état.

Une stratégie efficace est d'observer les motifs et les symétries dans la grille, s'il y en a, alors réaliser des actions symétriques : ampoule à droite puis ampoule à gauche etc.

La stratégie optimale est cependant de faire des calculs mathématiques d'algèbre linéaire qui permettent de résoudre mathématiquement toutes les grilles.

Le principe de résolution est mathématique, en modélisant le grille par une matrice $ [a_i] $ de taille $ n \times m $ et $ p \geq 2 $ états possibles.

En appuyant sur une case, certaines autres cellules ont leur état changé ou inversé (si $ p = 2 $)

L'état suivant est alors déterminé, pour chaque case $ i $, par le nombre de fois ou les cases sont appuyées (modulo $ p $)

Cet état peut se représenter avec $ m $ calculs $ a_{i1} x_1 + ... + a_{in} x_n) \mod p = 0 $ pour lequel la valeur des $ x_i $ est la solution recherchée.