Y a-t-il un algorithme pour le jeu "Flip all" (Light Out)?

Question

Dans ce jeu: http://www.mathsisfun.com/games/allout.html La fonction solve peut résoudre n'importe quel cas, peu importe comment vous "abusez" du plateau original. S'il vous plaît, dites-moi l'algorithme pour résoudre ce jeu. J'ai essayé de réfléchir pendant des jours mais je n'ai toujours pas trouvé de solution pour tous les cas.

D'accord, après avoir lu quelques réponses et commentaires (et jeté un coup d'œil rapide au jeu Light out), j'élargis ma question :

Le jeu sera-t-il différent si j'agrandis la taille de la grille (par exemple à 25x25) ? Existe-t-il toujours un algorithme possible pour résoudre n'importe quel cas, en un temps raisonnable (< 2s) ?

Answer 1

Ce jeu est plus communément connu sous le nom de Lights Out et possède un certain nombre de solutions élégantes, toutes basées sur des mathématiques standard mais quelque peu avancées. Je ne les décrirai pas toutes ici, mais si vous cherchez un peu sur Google, vous pourrez trouver toutes sortes d'explications allant de procédures simples à des transformations en algèbre linéaire ou en théorie des groupes. Quelques liens :

http://www.hamusutaa.com/pilot/solution.html

http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf

http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

Edit : En réponse à votre deuxième question. L'algorithme présenté dans le deuxième lien que j'ai posté peut résoudre un plateau de dimensions n x n en temps O(n^6), ce qui signifie que vous devriez être capable de résoudre rapidement un plateau de dimensions 25 x 25.

Answer 2

Comme la plupart des problèmes de "jeu" en IA, il y a une approche générale :

Implémentez une structure arborescente où chaque nœud est l'état du jeu et les enfants des états représentent les transitions entre ces états.

Effectuez ceci soit en utilisant une recherche en largeur (en profondeur est OK si vous gardez une trace des états passés que vous avez vus et refusez de les revisiter, et si vous ne vous souciez pas de trouver la solution optimale) soit en trouvant une heuristique optimiste qui vous permet d'utiliser A*. Une heuristique assez mauvaise à laquelle je pense est "Le nombre de cercles à retourner pour gagner le puzzle, divisé par 5." Je ne suis pas sûr s'il y en a une meilleure ; je serais intéressé d'entendre l'avis des gens là-dessus (Notez qu'elle doit être optimiste, c'est-à-dire que l'heuristique ne peut JAMAIS surestimer le nombre de mouvements nécessaires.)

Aller plus en détail est un peu absurde car il s'agit d'un sujet très vaste, et en plus de cela, c'est assez simple si vous savez comment faire une recherche en largeur ou A*.