Solveur Lights Out

Lights Out est un jeu électronique composé d'une grille de cases lumineuses (parfois avec des ampoules) ou numérotées (originellement de 5 par 5).

Au début du jeu, un motif de cases est allumé (différents états). En appuyant sur l'une des cases, elle bascule d'état (elle passe d'allumée à éteinte, ou d'éteinte à allumée ou change de 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.

Exemple : Un plateau de jeu à 2 états : 0 ou 1 est en position initiale :

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.

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.