Solveur Lights Out

Lights Out (ou Flip Tiles game) est un jeu électronique de réflexion composé d'une grille de cases lumineuses (parfois avec des ampoules ou des interrupteurs) 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.

A la main

— Travailler ligne par ligne (ou colonne par colonne) : commencer par résoudre la première ligne.

— Cliquer sur les cases de la deuxième ligne pour corriger les erreurs de la première.

— Répéter jusqu’à la dernière ligne.

Mathématiquement

— Représenter la grille (état initial du jeu) comme un vecteur $ \vec{b} \in \mathbb{F}_2^n $ (avec $ \mathbb{F}_2 $ le corps fini, 2 correpondant au nombre d'états)

— Construire la matrice $ A $ des effets de clics sur la grille ($ A_{ij} = 1 $ si le clic sur $ j $ affecte $ i $).

— Résoudre le système $ A \vec{x} = \vec{b} $ dans $ \mathbb{F}_2 $.

Avec un solveur

— Indiquer l'état initial de la grille et le nombre d'états possibles (généralement 2 pour noir/blanc ou allumé/éteint)

— Cliquer sur résoudre

Non, toutes les configurations ne sont pas solvables.

Si toutes les lignes sont résolues sauf la dernière ligne et qu'elle peut être éteinte en cliquant uniquement sur la dernière ligne, alors la configuration est solvable, sinon elle est insoluble.

Mathématiquement, la solvabilité dépend de l'image de la matrice $ A $. Une configuration $ \vec{b} $ est solvable si et seulement si elle appartient à l'image de $ A $ dans $ \mathbb{F}_2^n $

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 (dCode accepte toute tailles de grille carré ou rectangulaires)

— État de départ aléatoire ou défini : les lumières peuvent démarrer dans des configurations diverses (dCode accepte tout état initial)

— État final vide ou défini : les lumières peuvent devoir être dans une configuration finale précise (dCode n'accepte qu'un état final uniforme tout éteint ou tout allumé, mais il est possible de retrouver un état final défini en résolvant l'état initial puis l'état final : les changements d'états nécessaires pour éteindre une configuration sont les mêmes que pour l'allumer)

— Motif de croix ou personnalisé : le motif de croix des cases voisines peut être personnalisé pour affecter d'autres cases (dCode accepte tout motif 3x3, la case centrale peut également rester inchangée)

— Actions limitées : le nombre de changements d'état autorisé peut être restreint pour augmenter la difficulté (utiliser dCode pour obtenir la solution ayant le minimum de coups)

— Jeu chronométré : un compte à rebours peut ajouter un défi supplémentaire pour terminer le jeu dans un délai imparti (utiliser dCode pour obtenir la solution rapidement)

— Obstacles : certaines variantes introduisent des cases noires qui ne peuvent pas être changées d'état (dCode ne gère pas les cases inertes, mais si dCode fournit une solution, alors elle est valide qu'il y ait ou non des cases noires/vides, si dCode ne fournit pas de solution, essayer de changer l'état initial à 1 pour une ou plusieurs de ces cases)

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.