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

Maintenant, nous avons juste besoin de solutions pour un 4x4 avec emballage. Un exemple : {0000} {0000} {0000} {0000} En appuyant sur le coin supérieur gauche, on obtient : {1101} {1000} {0000} {1000} Oui, je sais que j'ai commencé avec toutes les lumières éteintes, mais c'était un exemple. Mais, pour suivre les directives, j'ai vérifié quelques solutions 7x7 avec une autre méthode donnée ici, certaines sont insolubles. Je suis actuellement en train de créer une table pour une matrice 4x4, car j'en ai obtenu certaines où j'ai dû "chasser les lumières" deux fois ou plus.

Here is the example in matrix form.
0000
0000
0000
0000 PRESS TOP LEFT

1101
1000
0000
1000

Vous voyez ce que je veux dire par envelopper ? Il suffit de demander, et je répondrai avec une réponse à une presse avec emballage.

Answer 2

Ce puzzle est présenté dans la quête DDO le linceul et est très facile à résoudre pour 3x3 - 4x4 et 5x5.

Le 4x4 est simple car il résout les problèmes en une seule passe. 3x3 et 5x5 requièrent un deuxième passage avec quelques instructions.

1er pour l'une ou l'autre des passes, il suffit de cliquer sur la bascule située juste en dessous des points lumineux de la rangée supérieure. répétez cette opération jusqu'à ce que vous atteigniez le bas

Pour les 4x4, votre problème est résolu

Pour 3x3, cela vous laissera avec des lumières allumées dans la rangée du bas, et peu importe si c'est 3x3 ou 5x5, vous vous concentrez juste sur les spots du bas à gauche (en ignorant les 2 spots de droite pour 5x5).

Maintenant, la partie amusante

Vous retournez à la rangée du haut dans la même colonne que les spots allumés dans les 3 derniers

Pour ceux de la colonne 1, vous appuyez sur la bascule en 1 et 2.

Pour celui de la colonne 3, c'est 2 et 3.

Pour celui de la colonne 2, c'est 1, 2 et 3.

Vous répétez cette opération pour chaque point éclairé, même si cela signifie qu'il faut répéter pour basculer la même

Donc X X 0 serait 1, 2 puis 1, 2, 3. X 0 X serait 1, 2 puis 2, 3

Etc

Ensuite, une fois que c'est fait, résoudre pour une dernière passe et le travail est fait.

Une méthode entièrement manuelle pour résoudre les puzzles 3x3, 4x4 et 5x5.

Answer 3

J'ai prouvé à ma satisfaction qu'aucune des solutions données ici n'est valable. En fait, il y a 5x5 cas qui sont totalement insolubles. Voici comment vous pouvez vous le prouver : Prenez un jeu de cartes et distribuez une matrice en utilisant des cartes rouges pour indiquer une lumière allumée et des cartes noires pour indiquer une lumière éteinte. Distribuez une matrice de la taille que vous souhaitez, puis essayez la technique décrite ici. J'ai essayé une matrice 5x5 et j'ai obtenu une rangée inférieure qui ne correspond PAS à celle qui est affichée ici. Cela signifie que cette matrice 5x5 est insoluble en utilisant l'algorithme "follow the lights". Un autre site affirme que la matrice 6x6 est toujours soluble. Là encore, en utilisant la méthode décrite ci-dessus - distribuer des cartes pour créer la matrice et utiliser l'algorithme "follow the lights", j'ai trouvé plusieurs matrices 6x6 qui n'étaient pas solubles avec cette technique. Vous pouvez faire tous les calculs que vous voulez, mais en pratique, LES SOLUTIONS DONNÉES ICI NE FONCTIONNENT PAS POUR TOUTES LES MATRICES.

En effet, seuls 25 % de tous les jeux sont résolubles. Ceux qui sont solubles le seront avec cette méthode.