Stratégie pour résoudre l'énigme "Lights Out" (extinction des feux)

Question

Extinction des feux est un puzzle basé sur une grille où chaque cellule a deux états : activé ou désactivé. Vous pouvez permuter l'état de n'importe quelle cellule, mais lorsque vous le faites, les cellules adjacentes (horizontalement ou verticalement) sont également permutées. Étant donné que la grille est initialisée avec des états aléatoires, l'objectif est de mettre toutes les cellules en état d'arrêt.

Cependant, je n'ai jamais été capable de développer une stratégie pour résoudre (à la main) ce type de puzzle. En général, je finis par échanger des cellules au hasard. Quels sont les types de stratégies disponibles pour résoudre ce jeu ?

Il existe de nombreuses variantes de ce puzzle, mais je ne m'intéresse qu'à la version classique.

Ce puzzle est disponible en plusieurs tailles de grille. Il est souhaitable, mais pas obligatoire, que les stratégies proposées fonctionnent sur toutes les tailles de grille.

Ma stratégie habituelle (et imparfaite) consiste à essayer de nettoyer rangée après rangée, du haut vers le bas. Malheureusement, je ne parviens pas à vider la dernière rangée, et je commence alors à échanger des cellules au hasard, ou simplement à ragequit tout à fait.

---

Il existe une implémentation open-source et multi-plateforme appelée flip dans le cadre de La collection de puzzles portables de Simon Tatham .

Answer 1

La méthode que je vais vous expliquer fonctionne techniquement pour n'importe quelle taille de grille, mais elle nécessite certaines connaissances que je ne sais pas comment déterminer à partir de zéro. Si vous voulez faire des recherches en ligne à ce sujet, cette méthode est généralement appelée "chasing lights" ou "chasing the lights".

Commencez par appuyer sur les boutons de la deuxième rangée correspondant aux cellules allumées de la rangée supérieure, puis sur les boutons de la troisième rangée correspondant aux cellules allumées de la deuxième rangée, etc. C'est exactement ce que vous faisiez déjà, en chassant les lumières jusqu'à la rangée inférieure, d'où le nom.

Comme vous le savez, le problème se pose lorsque la grille est vide, à l'exception de la ligne inférieure. À ce stade, le moyen de la finaliser est d'appuyer sur certains boutons spécifiques de la première rangée correspondant aux cellules éclairées de la rangée inférieure, puis de poursuivre les lumières vers le bas à partir du haut à nouveau. Si vous avez appuyé sur les bons boutons de la première rangée, lorsque vous aurez terminé la deuxième poursuite, le puzzle sera résolu.

Pour autant que je sache, vous devez juste savoir quels boutons appuyer sur la rangée du haut pour correspondre à un motif spécifique qui a été laissé sur la rangée du bas après la poursuite initiale. Si vous pouvez trouver une méthode pour déterminer les bons boutons à pousser sur la rangée supérieure, vous pouvez probablement utiliser une méthode très similaire pour généraliser cela à n'importe quelle taille de grille. Je ne connais pas de méthode pour cela cependant, donc je vais, euh, laisser cet exercice au lecteur.

Pour la version classique 5x5 du puzzle, il s'avère qu'il n'y a que 7 motifs possibles sur la rangée du bas après la poursuite initiale. Je vais donc simplement énumérer les 7 motifs possibles et les boutons correspondants de la première rangée sur lesquels appuyer pour chacun d'eux. Les boutons sont numérotés de gauche à droite.

|--------------------+-----------------|
| Left on bottom row | Push on top row |
|--------------------+-----------------|
| 1, 2, 3            |               2 |
| 1, 2, 4, 5         |               3 |
| 1, 3, 4            |               5 |
| 1, 5               |            1, 2 |
| 2, 3, 5            |               1 |
| 2, 4               |            1, 4 |
| 3, 4, 5            |               4 |
|--------------------+-----------------|

Des tables de correspondance similaires peuvent probablement être trouvées en ligne pour les autres tailles.

Answer 2

Je n'ai pas de stratégie, mais voici quelques informations sur le tableau 5×5 :

• L'ordre ne compte pas. Cliquer sur une tuile A, puis sur une tuile B est exactement la même chose que cliquer sur la tuile B, puis sur la tuile A - ou cliquer sur la tuile A, puis sur la tuile B, puis à nouveau sur la tuile A, puis à nouveau sur la tuile A, puis peut-être retourner une autre tuile, puis la tuile B.
  En bref, une tuile fait ou ne fait pas partie de la solution (un ensemble non ordonné de tuiles que vous devez échanger). Tourner en rond en essayant les mêmes mouvements encore et encore ne vous mènera nulle part.

  
  Si proche, et pourtant si loin

• Moins n'est pas plus. Tenter de minimiser la quantité de cellules éclairées/éteintes peut être contre-productif (voir l'image ci-dessus). Vous devriez plutôt essayer d'amener le jeu à une configuration que vous pouvez reconnaître et résoudre de mémoire.

• Les jeux symétriques ont des solutions symétriques. Gardez cela à l'esprit : reflétez vos mouvements et la complexité du jeu diminuera considérablement.

• Les solutions ne sont pas uniques, et la tuile centrale n'est jamais nécessaire. Bien que cela puisse faciliter la résolution d'une énigme, cela apparaît que tous les jeux solvables peuvent être résolus sans la tuile centrale.

Answer 3

Solution au 6x6 Lights Out :
La rangée inférieure d'un puzzle 6x6 peut contenir toutes les combinaisons possibles de lumières. Par conséquent, un tableau, similaire à celui que Chad Birch a fourni ci-dessus pour le puzzle 5x5, contiendrait 63 rangées. Cependant, vous pouvez résoudre n'importe quel puzzle Lights Out 6x6 avec ce petit tableau :

|--------------------+-----------------|
| Left on bottom row | Push on top row |
|--------------------+-----------------|
| 1                  |            1, 3 |
| 2                  |               4 |
| 3                  |            1, 5 |
| 4                  |            2, 6 |
| 5                  |               3 |
| 6                  |            4, 6 |
|--------------------+-----------------|

Pour toute combinaison de feux restants sur la rangée inférieure, il suffit de combiner les lignes du tableau ci-dessus, en se rappelant qu'appuyer deux fois sur un bouton revient à ne pas l'appuyer du tout. Par exemple, si la rangée inférieure contient
4, 5, 6
vous pousseriez
2, 6, 3, 4, 6
ou simplement
2, 3, 4,
puisque les deux 6 s'annulent.

Answer 4

La solution suivante fonctionne pour chaque grille m × n :

Considérez la grille donnée comme un vecteur dans un espace vectoriel de dimension m × n. Chaque valeur est soit 1 (si la lumière est allumée), soit 0 (si la lumière est éteinte). Vous pouvez maintenant considérer chaque poussée de cellule comme un vecteur dans cet espace vectoriel. Comme vous pouvez pousser m x n cellules différentes, vous avez m x n vecteurs différents. S'ils changent quelque chose dans une cellule, la valeur est 1, sinon 0.

Comme badp l'a mentionné, ce n'est intéressant que si vous devez appuyer sur un bouton ou non. Pas besoin de regarder l'ordre, pas besoin d'appuyer sur un bouton plus d'une fois. Vous avez donc une équation

vecteur pour votre grille = a_1 x cellvector1 + a_2 x cellvector_2 + ... a_mn x cellvector_mn a_1, a_2, ..., a_mn est soit 0 soit 1.

Comme vous avez m x n variables (a_1 ... a_mn) et m x n équations (les rangées des vecteurs), vous pouvez la résoudre avec Élimination gaussienne .

Si vous êtes allemand, vous pourriez vouloir lire " Exercice 2, 30e Concours fédéral d'informatique "

Answer 5

En jouant avec différentes tailles de jeu, j'ai trouvé quelques éléments qui ont piqué ma curiosité.

Tout d'abord, le cas 4 x 4 est trivial - il suffit de chasser les carrés éclairés et le problème est résolu au premier passage. Les cas 2 x 2 et 3 x 3 sont (curieusement) moins triviaux mais pas vraiment difficiles.

Deuxièmement, le cas 9 x 9 est presque trivial. Si nous numérotons les colonnes de 1 à 9 (de gauche à droite dans ma tête, mais l'un ou l'autre est parfait bien sûr), il n'y a que deux résultats après la première poursuite - soit il est résolu du premier coup (comme le cas 4 x 4), soit les carrés allumés de la rangée du bas sont 1, 3, 5, 7, 9 et si vous cliquez maintenant sur ces carrés de la rangée du haut et les poursuivez, il est résolu.

Le cas 7 x 7 semble céder à une stratégie très simple qui m'a pris une douzaine de parties à repérer. La première poursuite aboutit à toutes sortes de configurations différentes dans la ligne de fond - trop nombreuses pour être cataloguées de manière raisonnable. Cependant, après cette première descente, je peux choisir la ligne du haut de la manière suivante : pour chaque case i de la ligne du bas qui est éclairée, vous devez cliquer sur les cases de la ligne du haut i-1, i , i+1. Vous pouvez soit cliquer sur les cases en suivant cette règle, soit l'écrire pour toute la ligne et ensuite cliquer sur les cases qui apparaissent un nombre impair de fois - même chose mais sur papier. Après cela, il suffit de chasser les carrés et le travail est terminé. Il est clair que si la case 1 ou la case 7 est allumée, les résultats sont 1,2 ou 6,7 car il n'y a pas de 0 ou de 8. Cela fonctionne quand même.

A ce stade, j'ai essayé cette stratégie sur d'autres dimensions, 6, 8, 11, 12, 16 - et elle ne fonctionne pas sur ces dimensions. Elle est donc propre au cas 7 x 7 ou peut-être que la stratégie 7 x 7 est un cas particulier d'une méthode plus générale.