Bonsoir,

C'est un peu délicat car les bords jouent un rôle très particulier (on n'applique pas vraiment la même fonction au bord car il n'y a pas toutes les cases adjacentes). Ce serait plus facile si on considérait une grille de Pacman en recollant les côtés gauche et droit ensemble et le haut et le bas ensemble. Mais je vais y réfléchir sous cette forme.

Vu qu'on peut paver le plan avec des croix, je pense qu'il faut partir de là (en effet on va minimiser le nombre de coups si on ne fait le moins de chevauchement possible).

Si on s'autorise à jouer en dehors de la grille on peut faire beaucoup mieux que n^3.

Bonsoir,

Si on part du principe que chaque coup permet d'annuler au moins une case (en tenant compte des cases qui se voient réaffectées 1), on a en effet n² coups minimum. En dessous d'une annulation d'une case par coup, le coup est inutile (peut-être pas si inutile que ça mais d'un point de vue d'efficacité).
Bien sûr, on peut descendre a bien moins que n².

J'ai essayé de modéliser le problème par un graphe.
On peut associer la grille à un k-cube (k = n²). Une simple grille de dim 2 correspond à un tesseract. Mais, je ne vois pas comment passer d'une case à l'autre puisque dans l'hypercube, deux sommets sont reliés lorsqu'ils ne diffèrent que d'un unique chiffre alors que la transformation impose une modification d'au moins trois cases. Il faudrait trouver une représentation qui permette le calcul de la longueur d'une chaine.

En remarque à la croix, j'ai conçu le programme pour qu'il soit impossible de jouer hors de la grille. Ça aurait été trop facile !

Bonjour,

Il y a commutativité des coups; comme il ne sert à rien de jouer deux fois le même coup, le nombre maximum de coups est n².
Pour n=3 il y a une seule solution, en 5 coups: case centrale et les 4 cases aux angles.
Pour n=4 une étude informatique des 2¹⁶ possibilités donne 4 solutions (aux symétries près) en 4, 6, 8 et 10 coups. Le nombre minimum de coups est donc 4 en jouant par exemple les cases (1,3), (2,1), (3,4) et (4,2).
Pour n=5 je n'ai pas trouvé de solution: il y a 2²⁵ possibilités et mon programme est trop lent,je n'ai pas testé tous les cas.

Effectivement, on peut résoudre la grille de dim4 en 4 coups. Intéressant de savoir qu'une grille de dimension 4 se résout plus rapidement qu'une grille de dimension 3.
Merci de votre réponse.

Pouvez-vous me donner plus de détail concernant votre programme ?

J'ai pensé à associer la grille à un nombre binaire. Par exemple pour la grille de dimension 2, on aurait le nombre 1111.
A partir des transformations autorisées, on déduit des sommes 'autorisées'. Par exemple, pour le cas très simple de la sélection de la case (1;1) pour n = 1111, on aurait cette affectation :
n = (((n / 1000) + 1)%2)*1000 + (((n / 100) + 1)%2)*100 + (((n / 10) + 1)%2)*10 + (n + 0) %2;
et pour la case (1;2) :
n = (((n / 1000) + 1)%2)*1000 + (((n / 100) + 0)%2)*100 + (((n / 10) + 1)%2)*10 + (n + 1) %2;

Ce calcul de somme consiste à trouver le nombre minimale de sommes (des sommes différentes suivant les transformations et la case sélectionnée) pour annuler le nombre n.

Malheureusement, le programme doit ici travailler sur de trop grand nombre. Donc il y a obligation de travailler sur des matrices.

Bonjour,

Pour trouver toutes les solutions pour n=5 j'ai écrit un programme en turbo-pascal.
Il m' a donné en quelques minutes l'unique solution (à une symétrie près) en 15 coups:
11000,11011,00111,01110,01101.
Pour n=6 il y a 2³⁶ grilles à examiner et cela devient trop long.
J'ai alors testé la suite 1,4,5,4,15 dans l'encyclopédie des suites; j'ai trouvé la suite A75464 qui répond justement au problème posé: il s'agit du LIGHTS OUT PUZZLE.
Il y a plusieurs pages de l'encyclopédie des suites consacrées à ce problème.
En fait on obtient toutes les solutions en résolvant un système linéaire d'ordre n².

Bonsoir jandri,
Merci infiniment !
Je ne savais pas qu'une telle encyclopédie existait. Je vais regarder ça attentivement bien que mon anglais soit médiocre.

Aussi, je suis intéressé par la manière dont tu as trouvé la solution pour n = 5. Peux-tu m'écrire très rapidement le principe de ton algorithme ?

Bonjour NOxs,

Pour n=5 j'ai testé toutes les possibilités, chacune étant représentée par un entier binaire stocké dans un tableau a; je fais agir le tableau a sur un tableau b initialement formé de 1 puis je teste si tous les éléments de b sont devenus des 0.
Voici le programme en Pascal:
begin
for k:=1 to 33554431 do
begin
x:=k; for i:=1 to n do for j:=1 to n do
begin
b[i,j]:=1;a[i,j]:=x mod 2 ;x:=x div 2
end;
for i:=1 to n do for j:=1 to n do
if a[i,j]=1 then
begin
b[i,j]:=1-b[i,j];
if i>1 then b[i-1,j]:=1-b[i-1,j];
if i if j>1 then b[i,j-1]:=1-b[i,j-1];
if j end;
s:=0;for i:=1 to n do for j:=1 to n do
s:=s+b[i,j];
if s=0 then write(k)
end
end.

Salut,

La ligne b[i,j]:=1;a[i,j]:=x mod 2 ;x:=x div 2" est tout à fait intéressante ! C'est ce que je cherchais

Merci encore !

Salut,

Pour tester toutes les possibilités, il y a quelques conditions que l'on peut imposer sur les tableaux d'élimination (un peu moins que les 2^(n^2) possibilités). Par exemple

-> pour éliminer n^2 cases il faut au moins n^2/4 coups (donc au moins n^2/4 valeurs à 1 dans le tableau des coups)

-> il doit y avoir des 1 "un peu partout" dans le tableau

Je pense qu'il y en a d'autres, plus fine, qui permettrait de pousser un peu plus loin les calculs.

Pour n=6, j'ai pu faire tourner un programme sur une grosse machine. Il n'y a qu'une seule solution (qui est symétrique) :
101101
011110
111111
111111
011110
101101

Il faut donc 28 coups ! (et on a pas le choix !)

Ha ha ha... c'était débile : il suffit de résoudre un système linéaire. Le nombre de solution est simplement le rang de la matrice !

Je suis en train de coder l'algorithme pour la méthode de Gauss Jordan.
J'ai un problème pour la déclaration de mes tableaux. En effet, j'ai besoin d'un tableau à trois dimensions bien plus grand que [100][100][100]. Et en le déclarant en int ça à l'air de poser problème... J'ai essayer avec les autres types mais ca ne passe pas non plus.

100*100*100 = 1'000'000 ce n'est pas si gros pour un tableau ! J'ai aucun problème ni avec mon compilateur ni avec l'exécution du programme (qui intialise simplement le tableau).

J'ai même essayé avec un tableau 200*200*200 et aucun problème.

Pourtant il est vieux mon ordinateur (pentium 3, 256MO de RAM)

Salut à tous ,

Ce problème est en effet très amusant !!

il s'agit effectivement juste d'un système linéaire à coefficient dans
On définit n² variables qui valent 1 si on appuie sur la case associée et 0 sinon.

On a donc une application linéaire de dans qui a une grille initialement constitué de 0 associe la grille obtenu en ayant modifié les cases pour lesquelles (où les x_i,j sont les variables).

Une solution du problème est un n² uplet tel que .Le nombre de coups de la solution est alors le poids de Hamming du vecteur (c'est à dire le nompbre d'éléments non nuls).

Le plus simple est donc de calculer le noyau de l'application linéaire (le nombre de solutions du problème sera alors le nombre d'éléments du noyau, c'est-à dire 2 puissance la dimension)

Puis on calcule une solution particulière (avec Gauss Jordan par ex) puis on fait la somme avec tous les éléments du noyau pour trouver la solution de plus faible poids de Hamming.

Je ne pense pas qu'il y ait de formule explicite facile pour le nombre de coups de la meilleure solution. En effet, il y a des n pour lesquels l'application linéaire est bijective (il n'y a alors qu'une solution), des n pour lesquels il y a plusieurs solutions, et des n pour lesquels il n'y a pas de solution (si mes souvenirs sont bons).

a plus,

1emeu

Rectification : il y a toujours au moins une solution (mais ce n'est pas toujours le cas si on prend une grille de départ autre que celle remplie de 1)

a plus,

1emeu

Comment montres-tu qu'il y a toujours une solution ? Je suis preneur.

Je confirme pour l'unicité, le comportement de la dimension du noyau est pour le moins bizarre...

Pour ceux qui ne veulent pas me croire :
(les calculs ont été fait avec sage et la worksheet est disponible ici : )
4   :  4
5   :  2
6   :  0
7   :  0
8   :  0
9   :  8
10  :  0
11  :  6
12  :  0
13  :  0
14  :  4
15  :  0
16  :  8
17  :  2
18  :  0
19  :  16
20  :  0
21  :  0
22  :  0
23  :  14
24  :  4
25  :  0
26  :  0
27  :  0
28  :  0
29  :  10
30  :  20
31  :  0
32  :  20
33  :  16
34  :  4
35  :  6
36  :  0
37  :  0
38  :  0
39  :  32
40  :  0
41  :  2
42  :  0
43  :  0
44  :  4
45  :  0
46  :  0
47  :  30
48  :  0
49  :  8

Salut,
Ah intéressant ! Peux-tu expliciter le calcul du noyau 1emeu ? Je ne connais pas grand chose en calcul matriciel. Mais j'ai résolu le problème dans un cas général avec l'algorithme de gauss-jordan. Ca marche très bien !
Aussi que représente cette liste tringlarido ? C'est le nombre minimum de coups pour résoudre une grille de dimension n*n initialisée à 1 ? Si c'est le cas, je doute que tes valeurs soient justes ..

Ca n'a rien à voir avec le nombre de coups minimaux... C'est la dimension du noyau. Il correspond au défaut d'unicité de la solution à notre problème !

Ok !
J'ai pas compris a quoi servait le noyau .. c'est pour ca.

Pour le fait qu'il y a toujours au moins une solution je croyais avoir une preuve mais elle était fausse,... donc je ne sais pas comment faire. Mais je crois que ça a été montré.

Je continue à réfléchir au sujet

à plus

Salut,
J'ai presque terminé de coder l'algorithme de gauss-jordan.
J'arrive à obtenir la forme échelonnée de la matrice augmentée du système linéaire à n*m équations.
Ce qui me donne un truc du style pour une grille initialement remplie de 1 et pour n = m = 4 :
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 :0
0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 :1
0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 :1
0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 :0
0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 :0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 :0
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 :0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 :0
0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 :0
0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 :1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 :1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 :0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 :1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 :0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 :0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 :1

voilà je n'ai aucune idée de comment mettre sous forme de matrice unité la partie qui se situe avant les ":".
(les 0 se trouvent sur les dernières lignes compte tenu des permutations de mon algorithme)

Merci pour vos réponses

Tu ne peux pas tout simplement. Le noyau est de dimension 4 (voir plus haut), c'est normal qu'il y'ait quatre lignes de 0. Par contre il est plutôt inquiétant de voir que tu as à droites des ":" des chiffres 1 en face des lignes. Il doit y avoir une erreur quelque part car pour n=4 il y a des solutions au problème !

C'est normal qu'il y ait des 1 au dessus des 0. La réduction s'arrête lorsqu'il n'y a plus de pivot non nul. Je suis étonné qu'il n'y ait pas de méthode pour réduire la matrice à une matrice unité. Les résultats obtenus par mon programme corroborent ceux de la liste des dimensions du noyau.