On profite de cette occasion de pratiquer le formalisme mathématique. Regroupons donc les affirmations ainsi :

• Hypothèse (assertion proposée comme point de départ pour une enquête approfondie)
• Définition (explication du sens d’un mot ou d’une expression)
• Théorème (assertion forte)
• Lemme (assertion intermédiaire)
• Démonstration (assertion établissant la vérité d’un théorème ou d’un lemme. Le symbole □ dénotera la fin d'une démonstration.)
• Corollaire (assertion découlant directement d’un théorème ou d’un lemme)

Non. L’état d’une case dépend uniquement du nombre de clics effectués sur cette case et ses voisines, pas l’ordre des clics. Si le nombre de clics est pair alors l’état de la case reste inchangé, et si le nombre de clics est impair alors l’état de la case change.

Exemple :

Choisissez deux cases voisines, disons A et B. Ensuite, cliquez sur ces cases dans l’ordre A, B, B, A. Quel est le résultat? ↠ Rien n’a changé car B, B n’a aucun effet et A, A n’a aucun effet non plus.

Inversons l’ordre des deux premiers clics. Faites B, A, B, A. Quel est le résultat? ↠ Pareil, rien n’a changé. L’ordre des deux premiers clics n’importe pas. De même pour toute permutation de deux clics sur A et B. L’ordre n’est pas important.

Ce qui suit est une façon de réduire le nombre de clics.

On trouve une séquence de clics permettant d’allumer toutes les cases, en notant le nombre de clics faits sur chaque case. Après, on change tout nombre pair de clics en 0 et tout nombre impair en 1 clic. La séquence résultante aura le même effet et sera une solution.

Définition:On dit qu’une séquence de clics est « réduite » s’il y a au plus 1 clic sur chaque case. Le processus décrit ci-dessus s’appelle une « réduction ».

Une séquence peut comporter au plus un nombre de clics égal au nombre de cases dans la grille car on clique sur chaque case au plus 1 fois. Alors si la grille fait h cases de long et w cases de large, il y a h×w cases (lumières) et une séquence réduite peut comporter au h×w clics.

Étant donné que l’ordre des clics n’est pas important, il suffit de savoir pour chaque ampoule si elle est cliquée ou pas dans la solution. Alors il serait bien possible d’effectuer une recherche par force brute en essayant toutes les combinaisons de clics.

Si la grille contient h×w ampoules alors il y en a 2^h×w combinaisons (2 options pour chaque ampoule, soit elle est cliquée dans cette combinaison, soit elle n’est pas cliquée). Une telle recherche à force brute serait par contre beaucoup trop long pour être utile. Mais, sauf lors des concours, vous pouvez activer les « Remarques Utiles » qui indiqueront, lorsque vous effectuez un clic, si ce clic vous a permis de vous approcher de la solution. Si le clic a réduit le nombre de clics restants avant la résolution du casse-tête, c’est bien, sinon recliquez sur cette ampoule pour l’annuler.

Lemme :

Si toutes les cases d’une grille sont allumées et qu’on clique sur chaque case une seule fois, les cases dans les coins sont éteintes (O), les autres cases extérieures sont allumées (#), et toutes les autres cases sont éteintes (O) comme illustré dans cette grille 4 x 4 :

            # # # #      O # # O
            # # # #      # O O #
            # # # #      # O O #
            # # # #      O # # O

            before       after

Démonstration :

Tout d’abord, chaque case est cliquée une fois et donc elle change d’état une fois. Elle change d’état aussi quand on clique sur sa voisine.

Ainsi, si le nombre de cases voisines est pair, alors la case subit au total un nombre impair de changements d’état en plus. Alors cette case sera éteinte si elle était allumée au départ.

De même, si le nombre de cases voisines est impair, alors la case subit au total un nombre pair de changements d’état en plus. Alors cette case sera allumée si elle était allumée au départ.

Il suffit de compter le nombre de voisines de chaque case pour obtenir le lemme. □

Si on clique sur chaque case un nombre pair de fois alors la réduction (expliquée précédemment) donne zéro clics sur chaque case—alors ce n’est pas étonnant que toutes les cases restent allumées. Mais existe-t-il une séquence réduite de clics qui commence et termine avec toutes les cases allumées?

Définition :

On appellera « cycle » toute séquence réduite comportant au moins un clic où toutes les cases ont le même état avant et après la séquence.

Pour en chercher, on va commencer avec une grille où toutes les cases sont allumées au départ et à la fin. Ainsi a-t-on un cycle car l’état initial et final de chaque case est le même.

Une manière de trouver un cycle consiste à :

• Commencer avec toutes les cases allumées
• Identifier deux séquences réduites différentes qui éteignent toutes les cases
• Faire fusionner ces deux séquences à une séquence qui, pour une grille initiale où toutes les cases sont allumées, termine avec toutes les cases allumées
• Réduire cette séquence combinée pour obtenir un cycle. Le cycle résultant comporte forcément des clics car les deux séquences combinées étaient différentes, c.-à-d. au moins un clic d’une des deux séquences n’était pas dans l’autre. Ce clic sera dans la séquence combinée réduite.

Pour quelles dimensions de grille est-ce possible? Pour des dimensions données on peut répondre à cette question en formulant et résolvant un système d’équations algébriques linéaires. Vous pouvez en lire plus en consultant les références données plus bas.

Si on commence avec toutes les ampoules allumées (#) et qu’on clique sur chaque case une fois, on obtient, comme expliqué ci-haut :

            O # # O
            # O O #
            # O O #
            O # # O

Étant donné qu’on cherche un cycle, c.-à-d. une séquence qui commence et termine avec toutes les ampoules allumées, on peut essayer de cliquer une fois sur toutes les ampoules éteintes (représentées par O). Ceci a pour effet d’allumer ces ampoules éteintes et de laisser toutes les autres ampoules allumées aussi. Essayez-le vous-même !

Rappel : D’abord on a cliqué sur toutes les cases, ensuite on a cliqué sur toutes les cases diagonales. Alors on a cliqué deux fois sur les cases diagonales. La réduction de cette séquence annule les clics doubles sur les cases diagonales et seuls les clics sur les cases # dans la grille ci-dessus resteront. Alors chaque case est allumée au début et à la fin. Alors les 8 clics sur les # ci-dessus forment un cycle! YOUPI, on a trouvé un cycle! 🥳

Essayez-le pour vous convaincre que les cases d’une grille 4×4 restent inchangées quand on clique sur les 8 cases marquées par un # ci-dessus. C’est plus facile à voir quand on commence avec toutes les cases allumées.

Si on connaît un cycle alors ceci peut servir à réduire une séquence de clics.

Lemme :

Si on connaît un cycle de c clics et qu’on identifie une séquence dont n clics font partie du cycle, alors on peut remplacer ces n clics par les c−nclics qui ne font pas partie du cycle pour obtenir une séquence équivalente.

Démonstration :

Cette démonstration constructive montre comment construire une telle séquence.

Si on rattache la séquence au cycle, la séquence combinée résultante sera équivalente car le cycle ne change rien. Dans la séquence combinée on effectue n clics deux fois, une fois dans la séquence originale et une fois dans le cycle. Par réduction, c.-à-d. en supprimant ces clics doubles, la nouvelle séquence sera toujours équivalente (car la réduction crée des séquences équivalentes) et elle n’aura alors pas n clics mais c−nclics qui font partie du cycle. □

Corollaire :

Si c−n < n alors la nouvelle séquence est plus courte. Ce n’est le cas que si n > c/2. En mots : si une séquence partage plus de la moitié de ses clics avec un cycle, alors on peut raccourcir la séquence avec le cycle.

Exemple :

Tracez une grille 4×4où toutes les cases sont allumées et dressez une liste de 13 cases sur la grille. Cliquez sur les 13 cases sélectionnées et dessinez le résultat. (Pourquoi 13 et pas 12 ou 11? On verra ça toute à l’heure :-) ) Vérifiez maintenant lesquels parmi ces 13 clics font partie du cycle et dressez une nouvelle liste de clics où les clics du cycle sont remplacés par les autres clics dans le cycle. Recommencez avec toutes les cases allumées et effectuez cette séquence raccourcie de clics. Quel est le résultat? Vous devriez trouver que le résultat de la séquence raccourcie est le même.

Quel est le résultat?

Le résultat de cette séquence réduite devrait être comme avant.

Theorème :

Au maximum, une séquence de clics sur une grille 4×4peut se réduire à 12 clics.

Démonstration :

On a déjà appris qu’une séquence réduite sur une grille 4×4 peut comporter au plus 4×4=16 clics. On connaît un cycle de 8 clics pour la grille 4×4. Alors toute séquence peut contenir au plus 16−8=8clics qui ne font pas partie d’un cycle. Aussi, on a découvert qu’on peut réduire une séquence si la majorité des clics de la séquence font partie d’un cycle. Alors une séquence réduite et raccourcie peut contenir au plus :
     8   (clics qui ne font pas partie du cycle)
+ 8/2 (moitié des clics du cycle)
= 12 clics
sur une grille 4×4. □

Corollaire :

On peut résoudre avec au plus 12 clics tout problème où il faut allumer toutes les cases d’une grille 4×4.

Précisions :

Le théorème ne dit rien par rapport à l’existence d’une séquence de longueur 12 qui ne peut être réduite par des cycles. Il est bien possible que la longueur maximale soit 12, 10, ou 8. Le théorème dit seulement qu’il ne peut pas contenir plus de 12 clics.

On fait un clic sur toutes les ampoules qui ne figurent pas dans le cycle, en l’occurrence les 8 ampoules sur les diagonales. Ensuite, on choisit 4 ampoules dans le cycle, par exemple, une sur chaque côté en allant dans le sens horaire. On a donc effectué ces 12 clics, représentés ici par © :

            © · © ©
            © © © ·
            · © © ©
            © © · ©

ce qui résulte en la grille suivante :

            # O O #
            O # # O
            O # # O
            # O O #

Non. Déjà, on remarque que ces 4 clics

            · © · ·
            © · · ·
            · · · ©
            · · © ·

ont le même résultat :

            # O O #
            O # # O
            O # # O
            # O O #

Ça veut dire qu’on a découvert un nouveau cycle de 12+4=16 clics, YOUPI ! 🥳 Si on laisse tomber les clics doubles (© + © = ·), il ne reste que ce nouveau cycle de 12 clics :

            © · © ©       · © · ·       © © © ©
            © © © ·   +   © · · ·   =   · © © ·
            · © © ©       · · · ©       · © © ·
            © © · ©       · · © ·       © © © ©

Vérifiez par vous-même que ceci est bien un cycle.

La somme de deux cycles doit être un cycle elle-aussi, c.-à-d. elle ne change pas la grille :

            © © © ©       · © © ·       © · · ©
            · © © ·   +   © · · ©   =   © © © ©
            · © © ·       © · · ©       © © © ©
            © © © ©       · © © ·       © · · ©

Ce qui donne une version du cycle de 12 clics mais qui a été tourné de 90° dans le sens horaire. C’est donc le troisième cycle trouvé! Vérifiez-le par vous-même.

Les séquences

            © · © ©         · · © ·
            © · · ·   and   © © © ·
            · · · ©         · © © ©
            © © · ©         · © · ·

ont 8 clics chacun.

Est-ce qu’on peut les réduire à l’aide des 3 cycles trouvés ?

Chaque séquence superpose le cycle de 8 clics par 4 clics, et le cycle de 12 clics par 6 clics. Vérifiez par vous-même ces 6 assertions. Elles ne superposent chaque cycle que par la moitié des clics qu’il contient. Alors, si ces séquences ne peuvent pas être réduites par ces 3 cycles. Mais, il suffirait de rajouter un seul clic pour que ceci soit possible.

On fait alors une conjecture sans preuve :

Hypothèse :

La longueur maximale d’une séquence de clics sur une grille 4×4 qui ne peut être réduite par un cycle est 8.

Dans ce qui suit on considérera les grilles 5×5 et encore plus de symétries.

Comme pour les grilles 4×4, il faut

• Commencer avec toutes les cases allumées
• Cliquer sur chaque case une fois pour obtenir

                      O # # # O
                      # O O O #
                      # O O O #
                      # O O O #
                      O # # # O

• Cliquer sur toutes les cases diagonales une fois (donc un seul clic sur la case centrale). Le résultat: toutes les cases sont allumées.
• Réduire la séquence en annulant tous les clics doubles sur les diagonales, ce qui laisse 25−9=16clics marqués ici par un © :

                      · © © © ·
                      © · © · ©
                      © © · © ©      (1)
                      © · © · ©
                      · © © © ·

• Se féliciter, car on a trouvé un cycle. YOUPI!! 🥳

Essayez-le pour vous convaincre que les cases d’une grille 5×5 restent inchangées quand on clique sur les 16 cases marquées par un © ci-dessus. C’est plus facile à voir quand on commence avec toutes les cases allumées.

Théorème :

Au maximum, une séquence de clics sur une grille 5×5 peut se réduire à 17 clics.

Démonstration :

On a déjà appris qu’une séquence réduite sur une grille 5×5 peut comporter au plus 5×5=25 clics. On connaît un cycle de 16 clics pour la grille 5×5. Alors toute séquence peut contenir au plus 25−16=9clics qui ne font pas partie d’un cycle. Aussi, on a découvert qu’on peut réduire une séquence si la majorité des clics de la séquence font partie d’un cycle. Alors une séquence réduite et raccourcie peut contenir au plus :
     9   (clics qui ne font pas partie du cycle)
+ 16/2 (moitié des clics du cycle)
= 17 clics
sur une grille 5×5. □

Corollaire :

On peut résoudre avec au plus 17 clics tout problème où il faut allumer toutes les cases d’une grille 5×5.
Exemple d’un problème nécessitant la séquence la plus longue :
Commencez avec une grille 5×5 totalement allumée. Cliquez sur les 9 cases diagonales ainsi que sur 8 autres cases, par exemple celles à côté des coins. La position résultante est une position où il faut le plus grand nombre de clics, 17 clics, pour allumer toutes les cases.

Précisions :

Est-ce que ceci veut dire qu’il y a des séquences de 17 clics qui ne peuvent être réduites ?

Réponse :

Non, autant qu'on le sache.

Étant donné que la grille est rectangulaire, le motif formé par les ampoules allumées/éteintes pourrait être rationnellement symétriques de 90° ou de 180° ou il pourrait avoir une symétrie par rapport à l’une des axes horizontale ou verticale divisant le rectangle en deux.

Dans ce qui suit, l’idée est que la solution consiste d’un nombre de clics ayant une certaine symétrie et d’un nombre de clics n’ayant pas cette symétrie.

Comment faire des progrès ?Il faut obtenir de l’inspiration en faisant des clics, peut-être au hasard, jusqu’à obtenir une grille d’une apparence bizarre ou qui a une symétrie. Alors on se demande si cette séquence de clics pourrait être spéciale.

Supposez qu’on se retrouve avec une grille comme celle-ci :

…et qu’on a oublié comment on s’était rendu là. C’est facile à retrouver en activant « Remarques Utiles » et en cliquant chaque position. Si le nombre affiché dans « Remarques Utiles : Vous pouvez gagner dans XX clics au plus » a diminué, alors on note cette position, sinon on reclique cette même position. On retrouve ainsi cette solution où © indique un clic :

            · · · · ·
            © © © © ©
            · · © · ·      (3)
            · © · © ·
            © · © · ©

À voir ceci, on devrait s’étonner et ressentir un sens aigu de curiosité !

Pourquoi ?

Parce que la grille (2) a une symétrie par rapport à l’axe horizontale centrale mais la solution ne contient pas cette symétrie. Il est très rare qu’en mathématiques un problème symétrie soit résolu par une solution asymétrique.

Et maintenant ?

On devra poursuivre cette piste d’enquête en isolant les parties symétriques et asymétriques de (3).

On écrit donc (3) comme la somme d'une partie symétrique et d'une partie asymétrique.

        · · · · ·     · · · · ·     · · · · ·
        © © © © ©     · © · © ·     © · © · ©
        · · © · ·  =  · · © · ·  +  · · · · ·
        · © · © ·     · © · © ·     · · · · ·
        © · © · ©     · · · · ·     © · © · ©

Tout comme les chasseurs de trésors à la recherche de gemmes précieuses, nous les mathématiciens cherchons des objets uniques. La décomposition ci-haut n’est pas unique. Il y a plusieurs façons d’écrire la partie asymétrique comme une somme de parties symétrique et asymétrique.

Y a-t-il une décomposition unique ?

On peut la rendre unique en imposant que les clics asymétriques soient d’un seul côté de l’axe de symétrie.

On utilise © + © = · et on écrit donc

           · · · · ·     · · · · ·     · · · · ·     · · · · ·
           © © © © ©     · © · © ·     © · © · ©     · · · · ·
           · · © · ·  =  · · © · ·  +  · · · · ·  +  · · · · ·
           · © · © ·     · © · © ·     © · © · ©     © · © · ©
           © · © · ©     · · · · ·     · · · · ·     © · © · ©

           · · · · ·     · · · · ·
           © © © © ©     · · · · ·
        =  · · © · ·  +  · · · · ·
           © © © © ©     © · © · ©
           · · · · ·     © · © · ©

Les résultants étant prometteurs, on doit poursuivre l’enquête pour apprendre autant qu’on puisse en savoir.

Puisque la grille originale était symétrique et que la partie symétrique doit faire une grille symétrique, alors la séquence asymétrique doit elle-aussi faire une grille symétrique.

Quelle grille produit-elle?

        · · · · ·                               O O O O O
        · · · · ·                               O O O O O
        · · · · ·   (4)   generates the board   # O # O #   (5)
        © · © · ©                               O O O O O
        © · © · ©                               O O O O O

Vérifiez-le par vous-même !

On verra qu’il y a très peu de solutions asymétriques pouvant créer des grilles symétriques et où tous les clics peuvent se mettre sur un côté de l’axe de symétrie.

Et si on faisant le tour de la grille (5) pour la regarder et la solution (4) de l’autre côté ?

La grille a la même apparence (puisqu’elle a une symétrie de 180°), mais la solution devient :

                    © · © · ©
                    © · © · ©
                    · · · · ·      (6)
                    · · · · ·
                    · · · · ·

Alors (6) est encore une séquence asymétrique qui produit la même grille symétrique (5). Est-ce un accident ou est-ce que c’est le cas en générale ?

Voici une assertion générale:

Si un problème symétrique (ici (5), ayant une symétrie de 180°) qui a été produit par une séquence asymétrique (ici (4)) alors le fait d’effectuer une opération de symétrie (ici une rotation de 180°) sur cette séquence génère une nouvelle séquence asymétrique (ici (6)) qui crée la même grille (ici (5)).

Que se passe-t-il lorsqu’on effectue les deux séquences asymétriques ?

Après la première séquence (4), trois ampoules sont éteintes (dans la grille (5)) et après la deuxième séquence (6) ces 3 ampoules sont rallumées. Alors (4) + (6)

                    © · © · ©
                    © · © · ©
                    · · · · ·      (7)
                    © · © · ©
                    © · © · ©

Est un cycle à 12 clics! Encore un, YOUPI !! 🥳 Vérifiez par vous-même en effectuant ces 12 clics.

À quoi peut server ce nouveau cycle ?

Tout comme l’autre cycle de 12 clics, on peut utiliser ce cycle pour réduire des séquences de clics.

Est-ce qu’il est possible de réduire le cycle de 16 clics à l’aide du cycle de 12 clics ? Le résultat doit être un cycle car cycle + cycle = cycle.

Effectuer les deux cycles donne… (à cause de © + © = · )

                    · © © © ·     © · © · ©     © © · © ©
                    © · © · ©     © · © · ©     · · · · ·
                    © © · © ©  +  · · · · ·  =  © © · © ©      (8)
                    © · © · ©     © · © · ©     · · · · ·
                    · © © © ·     © · © · ©     © © · © ©

Ce qui doit donc être un cycle, et oui, au fait, c’est le cycle (7) tourné de 90°.

Est-ce que le cycle de 16 clics est lui-même la somme de deux solutions asymétriques d’un problème symétrique ?

Il y a 2 façons d’écrire le cycle de 16 clics comme une somme :

                    · © © © ·     · · · · ·     · © © © ·
                    © · © · ©     © · · · ·     · · © · ©
                    © © · © ©  =  © © · · ·  +  · · · © ©      (9)
                    © · © · ©     © · © · ·     · · · · ©
                    · © © © ·     · © © © ·     · · · · ·


                    · © © © ·     · · · · ·     · © © © ·
                    © · © · ©     © · · · ©     · · © · ·
                    © © · © ©  =  © © · © ©  +  · · · · ·      (10)
                    © · © · ©     © · · · ©     · · © · ·
                    · © © © ·     · · · · ·     · © © © ·

Chacune des deux séquences du côté droit de (9) est une séquence asymétrique qui résulte en la grille symétrique

                    # O O O O
                    O O O O O
                    O O O O O      (11)
                    O O O O O
                    O O O O #

Chacune des deux séquences du côté droit de (10) est une séquence asymétrique qui résulte en la grille symétrique

                    # O O O #
                    O O O O O
                    O O O O O      (12)
                    O O O O O
                    # O O O #

Alors le cycle de 16 clics est la somme de deux solutions asymétriques d’un problème symétrique, et ça, de deux manières différentes.

Si on veut minimiser le nombre de séquences à retenir alors il suffit de se rappeler

                    · · · · ·
                    © · · · ·
                    © © · · ·      (13) 
                    © · © · · 
                    · © © © · 

Car l’autre séquence sur la droite de (9) a le même effet et les séquences sur la droite de (10) ne sont que des sommes de (13) et des rotations de 90° de (13).

Et comment est-ce que ceci peut faciliter la résolution de grilles symétriques ?

S’il est vrai que pour les grilles 5×5 les séquences (4), (13), et leurs rotations de 90° sont les seules séquences symétriques produisant des grilles symétriques par rapport à une axe (à part des clics symétriques produisant d’autres séquences asymétriques) alors pour résoudre une telle grille il suffit d’effectuer des clics jusqu’à ce que les ampoules soient toutes allumées, ou jusqu’à obtenir une des grilles (5) ou (11) (ou des rotations de 90° de ces dernières) pour ensuite effectuer les séquences (4) ou (13) (ou des rotations de 90° de celles-ci).

Autrement dit, pour résoudre une grille ayant une symétrie par rapport à une axe, il suffit d’essayer des combinaisons symétriques d’un nombre minimal de clics nécessitant donc un arbre de recherche plus petit.

On ne répondra pas à cette question, mais on a deux suggestions :

Hypothèse :

Il n’existe pas d’autres cycle pour une grille 5×5 qui ne soit pas une combinaison des 3 cycles avec 12, 12, et 16 clics.

Hypothèse :

La longueur maximale d’une séquence réduite de clics sur une grille 5×5 est 13.

On vous laisse le travail de penser à une preuve ou contrexemple de la forme d’un autre cycle indépendant ou d’une séquence de plus de 13 clics qui ne peut être réduite avec les 3 cycles (7), (8), et (1) ayant respectivement 12, 12, et 16 clics. La première hypothèse peut être vérifiée à l’aide de l’algèbre linéaire (voir plus bas), mais une preuve simple ou un cycle différent serait une belle trouvaille. Un exemple d’une séquence de 13 clics qui ne peut être réduit avec les 3 cycles est

            © · © · ©
            · © · © · 
            © · © · ©
            · © · © · 
            © · © · ©

À vous de vous amuser à rechercher et prouver ces hypothèses !

Avec h×w ampoules il y a 2h×w motifs d’ampoules allumées/éteintes possibles. Comme on a déterminé plus haut, il y a aussi 2h×w séquences de clics possibles.

Ceci dit, il y a des séquences qui produisent la même grille, en l’occurrence toute séquence et cette même séquence + un cycle. Alors on a plus de séquences que de motifs de grille atteignables, ce qui veut dire que, logiquement, il existe des motifs de grille qu’on ne peut pas réaliser.

Les mathématiques ont des mots pour décrire de telles situations. Si chaque séquence de clics produisait un motif différent, alors on appellerait « injective » la carte reliant des séquences aux motifs qu’elles produisent.

Comment se préparer aux questions lors des concours ?

Pour se préparer à ce jeu lorsqu’il figure comme question interactive, il peut être utile de commencer avec une grille où toutes les ampoules sont allumées. Pour obtenir une telle grille, on réduit à 0 le « Nombre de Coups Minimum » et « Ampoules violettes » et on augmente les dimensions de la grille. Puis, faites 2 clics, soit sur des ampoules adjacentes, soit sur des ampoules adjacentes diagonalement. Essayez de vous rappeler le motif résultant pour pouvoir le reconnaître lorsqu’il apparaît au cours d’une partie. Retentez ceci dans un coin de la grille, au milieu de la grille, et sur son bord pour voir comment ce motif change selon la position.

Une autre méthode de préparation consiste à prendre une grille 5×5 complètement allumée et à cliquer sur des ampoules qui sont symétriques par rapport à une diagonale ou la ligne centrale ou qui sont des versions tournées de 90° ou de 180° pour voir quel motif symétrique en résulte.

Que devra-t-on essayer d’abord s’il y a un petit groupe d’ampoules éteintes proches les unes des autres ?

Dans ce cas, on devrait essayer d’abord des coups dans ce centre de tels petits regroupements, car des clics sur le bord de tels regroupements ne feraient qu’éteindre des ampoules et augmenter le nombre d’ampoules éteintes. Si ceci ne marche pas, alors il faut cliquer sur des ampoules plus excentrées et cliquer un peu partout sur la grille.

Et si la grille a une symétrie ?

La grille de départ pourrait avoir une symétrie, par exemple par rapport à une ou deux de ses diagonales, ou par rapport aux axes de symétrie verticale ou horizontale. Sinon, des symétries rotationnelles de 90° ou de 180° sont possibles aussi. Dans la section « Quel rôle joue la symétrie… » on a dérivé la stratégie suivante.

On effectue des groups de clics symétriques qui préservent la symétrie de la grille jusqu’à ce que les ampoules soient toutes allumées, ou jusqu’à obtenir (si la grille est de dimensions 5×5) une des motifs suivants :

                    O O O O O            # O O O O             # O O O #
                    O O O O O            O O O O O             O O O O O
                    # O # O #  (5) or    O O O O O  (11) or    O O O O O  (12)
                    O O O O O            O O O O O             O O O O O
                    O O O O O            O O O O #             # O O O #

(ou des rotations de 90° de ces grilles) et puis on effectue tout simplement les séquences suivantes :

                    · · · · ·            · · · · ·             · © © © ·
                    · · · · ·            © · · · ·             © · © · ©
                    · · · · ·  (4) resp  © © · · ·  (13) resp  © © · © ©  (1)
                    © · © · ©            © · © · ·             © · © · ©
                    © · © · ©            · © © © ·             · © © © ·

(respectivement des rotations de 90° de ces séquences)

Ça veut dire quoi « Jouer de manière symétrique ? »

Si une case sur la ligne de symétrie est éteinte, il faut la cliquer. La raison : si on ne la cliquait pas, alors on devrait cliquer sur une case voisine pour l’allumer, mais il faudrait donc cliquer sur la sœur symétrique de cette voisine, ce qui aurait pour effet de changer deux fois l’état de la case sur la diagonale qui resterait donc éteinte.

Par le même raisonnement, il ne faut pas cliquer sur toute case allumée sur cette diagonale.

Si la position est symétrique par rapport à deux lignes de symétrie (2 diagonales ou la ligne centrale horizontale et verticale), alors les règles ci-dessus s’appliquent aux deux lignes. Il faudra cliquer sur toute case éteinte sur une ligne et ne pas cliquer sur toute case allumée. Ainsi, on trouvera une solution symétrique et on allumera toutes les ampoules.

Si la grille n’est pas symétrique par rapport à une axe mais elle a une symétrie rotationnelle, alors on effectue des groupes de clics qui préservent cette même symétrie rotationnelle.

Pour tout type de symétrie, lorsqu’on clique sur une ampoule, il faut cliquer sur les ampoules correspondantes (selon le type de symétrie) aussi. Autrement dit, s’il s’agit d’une symétrie de 90° alors on clique sur les 3 autres ampoules correspondantes. S’il s’agit d’une symétrie de 180°, alors on clique sur l’autre ampoule correspondante. Pour une symétrie par rapport à une axe, alors on clique sur l’ampoule de l’autre côté de l’axe. Pour une ampoule qui est son propre réflexion par rapport à la symétrie, alors on ne la clique qu’une seule fois. Par exemple, l’ampoule centrale pour tous les types de symétrie, ou une ampoule sur une diagonale lorsque la grille est symétrie par rapport à cette diagonale (pareil pour les lignes centrales verticale et horizontale).

Si, après avoir cliqué sur une ampoule et ses sœurs symétriques, la symétrie augmente (il y apparaît une nouvelle axe de symétrie) alors on utilise désormais cette nouvelle symétrie aussi.

Et si la grille n’a aucune symétrie ?

Si la grille ne contient aucune symétrie alors on peut essayer de faire des clics qui allument plus d’ampoules qu’ils n’éteignent. Puis, on peut faire des clics qui font rapprocher les ampoules éteintes. Tôt ou tard, on finira par créer une position symétrique après laquelle on peut poursuivre la solution avec des clics symétriques.

Pour lire l’histoire du jeu ainsi que les grandes lignes d’une stratégie de solution, vous pouvez consulter la page Wikipédia en anglais. Pour une description plus mathématique avec plus de références, visitez Wolfram Mathworld. Vous pourriez vérifier si nos trouvailles figurent déjà sur ces pages.

On peut répondre à cette question en formulant et résolvant un système d’équations algébriques linéaires. Vous pouvez en lire plus en suivant les références données plus haut.

Les ampoules violettes peuvent tout changer. Il faudrait vérifier pour toutes les assertions ci-haut si elles sont valides ou pas lorsqu’il y a des ampoules violettes, ou modifier ces assertions pour qu’elles restent vraies. L’algèbre linéaire sera assez flexible et générale pour décrire des grilles avec des ampoules violettes.