Afin de cotrôler finement la façon dont on "colore" le tableau, la technique d'utilisation de la cellule imédiatement située en dessous de la cellule que l'on souhaite colorer est évidente. La précision de cette méthode permet à coup sur de setter correctement les 4x5=20 premières cellules.
Mais le constat arrive vite, la résolution du jeu n'est pas au rendez-vous (dans un jeu de ce type de dimension 2, c'est le cas quand la matrice est carrée et constituée d'un nombre N de cellules en hauteur et largeur impair, à l'inverse d'une version comportant un nombre N pair).
En expérimentant un peu, on se rend rapidement compte que peu importe le sens ou l'ordre (de gauche à droite, l'inverse, ou au hazard) dans lequel on colore les cellules ligne après ligne. Le résultat de la 5eme ligne est toujours identique.
Il nous faut donc une technique qui nous permetrait de modifier la dernière ligne du tableau afin d'en déduire un systeme de controle du jeu et donc nous permettre de le résoudre
Vien donc le moment de l'expérimentation plus poussée : en faisant une modification sur l'une des cellules de la première ligne puis en réutilisant la technique ci-dessus, le résultat obtenu sur la dernière ligne est différent.
Imaginons alors que nous limitions notre choix aux cellules de 1 à 5 de la première lignen sur lesquelles nous souhaitions appliquer des modifications. Chaque cellule pouvant prendre 3 valeurs différentes (R, V, B) nous avons 3x3x3x3x3 = 3⁵ = 243 possibilités différentes.
Le nombre de possibilité est relativement conséquent à explorer manuellement, je commence alors par une version simplifiée du problème, celle qui consiste à ne considérer qu'un seul clic par cellule, sur l'ensemble des 5 premières cellules de la première ligne. 2⁵ = 32 possibilités, bien plus raisonable ! Je procède alors à une exploration exhaustive des résultats obtenus sur la ligne No. 5 en fonction de la configuration choisie pour la ligne No. 1
Le schema ci-dessous récapitule l'intégralité des résultats
Les résultats obtenus sur la ligne 5 sont en quantité très restreintes. 9 possibilités de codage (alors qu'il y aurait pu y en avoir un maximum de 32 après tout). Plusieures entrées différentes convergent donc vers des solutions identiques.
Celà rappelle la démonstration faite par Marlow Anderson & Todd Feil en 1998.
Par ailleurs, une configuration nous sera inutile, la configuration à résultat nul (en bas à gauche sur le schéma) obtenu logiquement lorsque l'on n'agit pas sur la première ligne (00000) mais également pour les cas 10100 et 00101. Celà réduit donc le nombre de possibilités de résolution.
L'on constate également que chaque symétrique d'une entrée donnée donne un résultat identique en sortie.
Par exemple, 00111 donne le même résultat (10201) que 11100.
Cette constatation est généralisable à toutes les entrées.
Ce constat est interessant car il diffère de ce qui se passe sur un jeu de ce type de dimension 2. En un sens, il simplifie la recherche de solution. Le Lights Out de dimension 3 sera potentiellement plus simple à résoudre que sa version initiale de dimension 2.
Le dernier constat est que l'ensemble E des 8 configurations de sorties trouvé est complet.
lorsqu'on cherche à créer une nouvelle configuration en combinant ces sorties ensembles (a l'aide de l'arithmétique modulaire en base 3) on obtient une configuration appartenant à l'ensemble initial.
ex : 10201 + 01010 = 11211 ∈ E
Il ne faut pas oublier qu'initialement il y avait 243 possibilités. La première approche a consisté à tester une dizaine de codes au hazard pour voir s'il y a un schema qui se dessine.
Les codes tirés au sort sont :
01201, 01210, 20101, 02120, 02220, 02000, 22001, 21002, 12012, 20102
et les résultats sont respectivement
22122, 22122, 12221, 22122, 01010, 20102, 20102, 01010, 12221, 00000
On constate dans l'échantillon que les résultats appartiennent à l'ensemble E et aucune nouvelle série n'apparait. On remarque également que quelques soit l'assymétrie de l'entrée, il y a une symétrie à la sortie.
Nous avons une conjecture, et à défaut de démonstation, nous allons obtenir une preuve en créant un algorithme de résolution de l'ensemble des entrées possible.
Force est de constater qu'il n'y a aucun nouvel éléments n'appartenant pas à l'ensemble E !
Celà veux donc dire que l'ensemble des configurations possible de la matrice n'est pas possible. Celà veux également que nous avons une solution simple à notre problème.
Nous avons à présent en main la possibilité de résoudre ce jeu par une méthode proche de l'élimination de Gauss-Jordan. Comme indiqué dans le walkthrough, nous settons correctement les 4 premières lignes à l'aide des lignes 2 à 5, puis agissont sur la ligne 1 et recommençons. Vu que le nombre de configurations de la ligne 5 est limité (ensemble E) et cohérent, nous en déduisons donc que 2 passages serons nécéssaire et suffisant pour résoudre ce jeu. La solution simplifiée est disponible ici.