Solveur Lights Out

Lights Out est un jeu électronique composé d'une grille de cases lumineuses 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 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.

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)

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.