Un casse-tête qui cache de l'algèbre linéaire
Lights Out se joue sur une grille 5 × 5 : chaque clic bascule la cellule visée et ses quatre voisines orthogonales, et le but est de tout éteindre. Derrière cette règle enfantine se cache une structure mathématique très nette. Je m'en sers ici comme prétexte pour montrer qu'un « petit jeu » se ramène souvent à un modèle exact, calculable, plutôt qu'à du tâtonnement.
Deux clics identiques s'annulent — bienvenue dans GF(2)
Première observation décisive : cliquer deux fois la même cellule revient à ne
rien faire, et l'ordre des clics n'a aucune importance. Seule compte, pour chaque
cellule, la parité du nombre de fois où on l'a pressée : zéro ou
une. On travaille donc dans le corps à deux éléments, noté GF(2),
où l'addition est le ou exclusif (1 + 1 = 0). Une solution
n'est pas une séquence de gestes, mais un simple sous-ensemble de cellules à
presser une fois chacune.
Le jeu tout entier tient dans un système d'équations
Chaque cellule de la grille impose une contrainte : la somme (modulo 2) des
pressions qui l'affectent — la sienne et celles de ses voisines — doit égaler son
état allumé/éteint de départ. Vingt-cinq cellules, donc vingt-cinq équations à
vingt-cinq inconnues (presser ou non chaque cellule). Tout se résume à une
équation matricielle A·x = b sur GF(2), où
A encode « qui bascule quoi », b l'état initial et
x la solution recherchée. Le jeu n'est plus un labyrinthe d'essais :
c'est un système linéaire.
Pourquoi certaines grilles sont insolubles
Sur une grille 5 × 5, la matrice A n'est pas inversible : son noyau
contient des configurations non nulles. Concrètement, certaines combinaisons de
clics ne changent rien à la grille, et par symétrie certaines
configurations de départ n'admettent aucune solution. C'est
pour cette raison que je ne tire jamais un état allumé au hasard : je pars de la
grille éteinte et j'applique des clics aléatoires. Une grille obtenue ainsi est
soluble par construction — l'ensemble des clics qui l'a produite est déjà, à la
parité près, une solution.
Un solveur par élimination de Gauss mod 2
L'indice (touche H) ne devine rien : il résout. Je monte la matrice
augmentée [A | b] et j'applique l'élimination de
Gauss, adaptée à GF(2) : plus de division ni de
soustraction, chaque pivot se propage par un simple ou exclusif de
lignes. Astuce d'implémentation : chaque ligne de vingt-six bits (coefficients +
second membre) tient dans un seul entier, et l'élimination se fait à coups
d'opérations bit à bit — quelques microsecondes pour la grille entière. La
solution obtenue indique exactement les cellules à presser.
Le vrai livrable : trouver le bon modèle
Ce que ce jeu illustre dépasse le casse-tête. Face à un problème qui semble appeler de la force brute, l'enjeu est de reconnaître la structure sous-jacente et de choisir la représentation qui la rend calculable — ici, un système linéaire résolu en temps constant plutôt qu'une recherche exponentielle. Sur vos projets, c'est ce réflexe qui distingue une fonctionnalité qui tient à l'échelle d'un bricolage qui s'effondre : j'investis le temps de modéliser juste, pour livrer une solution à la fois simple, rapide et démontrablement correcte.
