Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

Recherche d'une solution minimale d'un petit jeu

Posté par
N0xs
08-11-08 à 23:36

Bonjour à tous !
Je suis en première année de licence MPI à la faculté d' Orsay.

Voila, j'ai un petit jeu à réaliser en langage C.
On donne une grille de longueur n, remplie uniquement de 1.
Une fonction permet, en sélectionnant une case, de changer sa valeur ainsi que des cases latérales, supérieure et inférieure.
Si la valeur de la case à modifier est 1, alors on lui affecte la valeur 0 et 1 sinon.
Par exemple, on aura en sélectionnant la case centrale, la transformation suivante :
111
110
111

101
001
101
La victoire est obtenue lorsque toutes les cases valent 0.

Le programme est vraiment très simple. Et j'ai trouvé qu'il serait plus amusant de préciser le nombre de coups minimal pour gagner.
J'ai essayé de modéliser le problème par un graphe ... sans succès.

J'ai l'impression que ce nombre minimal vaut n² + 3*(n - 2). Mais il n'y a aucune chance que ma conjecture soit juste puisque je l'ai faite a partir des résultats obtenus avec n = 2, n = 3 et n = 4 et elle est fausse pour n = 1. Je n'ai même pas réussis a trouver une solution pour n = 5 (ce n'est pas particulièrement évident )
J'ai écris un programme qui 'tente' de résoudre la grille en sélectionnant 'au hasard' les cases à modifier. Et je n'arrive pas à obtenir une résolution en 16 coups ou moins après plus d'un milliard d'essais.
Donc, oublions le n² + 3*(n - 2).

A partir de là, je suis totalement démunis et je fais appel aux mathématiciens du forum !

édit Océane : forum modifié

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 08-11-08 à 23:42

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.

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 08-11-08 à 23:50

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.

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 09-11-08 à 00:53

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 !

Posté par
jandri Correcteur
re : Recherche d'une solution minimale d'un petit jeu 09-11-08 à 11:57

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 n2.
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 216 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 225 possibilités et mon programme est trop lent,je n'ai pas testé tous les cas.

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 09-11-08 à 12:34

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.

Posté par
jandri Correcteur
re : Recherche d'une solution minimale d'un petit jeu 09-11-08 à 19:44

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 236 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 n2.

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 09-11-08 à 22:47

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 ?

Posté par
jandri Correcteur
re : Recherche d'une solution minimale d'un petit jeu 10-11-08 à 18:14

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.

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 10-11-08 à 19:33

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 !

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 10-11-08 à 20:30

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.

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 11-11-08 à 22:33

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 !)

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 11-11-08 à 23:10

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 !

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 00:01


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.

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 00:12

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)

Posté par
1emeu
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 18:47

Salut à tous ,

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

il s'agit effectivement juste d'un système linéaire à coefficient dans \mathbb{F}_2
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 f de \mathbb{F}_2^{n^2} dans \mathbb{F}_2^{n^2} qui a une grille initialement constitué de 0 associe la grille obtenu en ayant modifié les cases pour lesquelles x_{i,j}=1 (où les x_i,j sont les variables).

Une solution du problème est un n² uplet (x_{1,1},\ldots,x_{n,n}) tel que f(x_{1,1},\ldots,x_{n,n})=(1,1,1,1,...,1).Le nombre de coups de la solution est alors le poids de Hamming du vecteur (x_{i,j}) (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

Posté par
1emeu
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 18:51

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

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 19:06

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...

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 12-11-08 à 19:55

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

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 14-11-08 à 20:31

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 ..

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 14-11-08 à 22:51

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 !

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 14-11-08 à 23:08

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

Posté par
1emeu
re : Recherche d'une solution minimale d'un petit jeu 15-11-08 à 10:21

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

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 15-11-08 à 22:13

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

Posté par
tringlarido
re : Recherche d'une solution minimale d'un petit jeu 15-11-08 à 22:29

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 !

Posté par
N0xs
re : Recherche d'une solution minimale d'un petit jeu 16-11-08 à 11:04

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.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !