Problème un peu "Taquin"

**Wardock** · 26/04/2012, 14h40

Bonjour à tous,

Alors voilà, je viens consulter les Dieux de MATLAB (

) Parce que j'ai un sale problème ! Un problème du genre qui rend dingue parce que terriblement simple, et terriblement obscur à la fois.. JE SAIS QUE VOUS VOYEZ DE QUOI JE PARLE !

DONC, laissez-moi vous expliquer ce problème qui est le mien :
Je suis censé réaliser un programme capable de résoudre n'importe quel Taquin sous forme matricielle (un taquin, c'est ça : http://fr.wikipedia.org/wiki/Taquin ). Bref, je commence par le commencement en confectionnant un sous-programme permettant de déplacer le vide (matérialisé par "0" dans la matrice du Taquin) de manière verticale et horizontale, voir les 2 à la fois si besoin.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function Z=bouge(M,lb,cb);
%FONCTION : Remplacer la case de coordonnées (ligne lb,colonne cb) par le 0, en décalant de manière réaliste les autres éléments.
 
[l0,c0]=find(M==0);  %Cherche l'élément 0 dans la matrice M
 
%2 cas sont possibles : "Le zéro est à droite" ou "le zéro est à gauche"
 
if c0>cb %Zero à droite
 
    while c0~=cb;
        c=M(l0,c0-1);
        M(l0,c0-1)=M(l0,c0);
        M(l0,c0)=c;
        [l0,c0]=find(M==0);
    end
 
elseif c0<cb %Zero à gauche
    while c0~=cb;
        c=M(l0,c0+1);
        M(l0,c0+1)=M(l0,c0);
        M(l0,c0)=c;
        [l0,c0]=find(M==0);
    end
end
 
 
%2 cas sont possibles : "Le zéro est au dessus" ou "le zéro est en dessous"
 
if l0>lb %Zero au dessus
    while l0~=lb;
        l=M(l0-1,c0);
        M(l0-1,c0)=M(l0,c0);
        M(l0,c0)=l;
        [l0,c0]=find(M==0);
    end
 
elseif l0<lb %Zero en dessous
    while l0~=lb;
        l=M(l0+1,c0);
        M(l0+1,c0)=M(l0,c0);
        M(l0,c0)=l;
        [l0,c0]=find(M==0);
    end
end
disp(M)

En entrée lb et cb sont les coordonnées de l'endroit où je souhaite amener mon 0
Et c'est là que ça foire (!!!) : Quand je lui demande un déplacement de gauche à droite (ou inversement) simple, il prend des chemins étranges au lieu de simplement faire passer le 0 de case en case sur la même ligne.. (j'espère que je suis assez clair) Et ça, ça m'embête beaucoup, parce que chaque déplacement devra être expliqué par le programme final : les détours sont parasites.
Exemple de détour :

     3    10     5     6
     8     1     4     2
    11     0    13    14
    10     9     7    15

Le déplacement de (3,2) à (3,1) donne :

     3    10     5     6
    11     8     4     2
     0     1    13    14
    10     9     7    15

On voit bien que les 0 est passé par la 2e ligne puis s'est décalé à gauche pour redescendre ensuite.. STUPIDE !

Quelqu'un aurait-il une idée de la raison de ces "détours" ?
Merci (INFINIMENT) d'avance à tous !

Peter

**Jean Dumoncel** · 26/04/2012, 16h25

Envoyé par Wardock

Alors voilà, je viens consulter les Dieux

Envoyé par Wardock

de MATLAB (

)

Dieu tout court ça suffisait...

Envoyé par Wardock

Bref, je commence par le commencement en confectionnant un sous-programme permettant de déplacer le vide

Effectivement, il va falloir des pouvoirs divin pour "déplacer le vide"!!

J'ai testé ton code et je n'obtiens pas le même résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
>> M = [ 3    10     5     6
     8     1     4     2
    11     0    13    14
    10     9     7    15]
>> bouge(M,3,1)
     3    10     5     6
     8     1     4     2
     0    11    13    14
    10     9     7    15

L'échange entre 11 et 0 a l'air correct.

Je n'ai pas regardé ton code en détail si ce n'est qu'il y a une erreur avec Z qui n'est pas définie dans la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function M=bouge(M,lb,cb)

**Wardock** · 27/04/2012, 15h13

Hummm.. C'est TELLEMENT bizarre !
En tout cas merci beaucoup pour ta réponse et d'avoir essayé, cependant, je pense que par "chance" tu es tombé sur un déplacement qui fonctionne..

Tu peux essayer avec ça s'il te plaît ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
     0    10     5     6
     3     1     4     2
     8    11    13    14
    10     9     7    15
 
>> Bouge2(M,1,4)
     3    10     5     0
     8     1     4     6
    11    13    14     2
    10     9     7    15

(De mieux en mieux, un détour de 2 lignes pour juste déplacer le 0 sur la ligne du dessus..)
Merci encore !

Invité · 27/04/2012, 15h27

Bonjour,

Pareil que magelan pour les deux cas présentés :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
M = [3    10     5     6
     8     1     4     2
    11     0    13    14
    10     9     7    15];
bouge(M,3,1)
 
ans =
 
     3    10     5     6
     8     1     4     2
     0    11    13    14
    10     9     7    15

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
M = [0    10     5     6
     3     1     4     2
     8    11    13    14
    10     9     7    15];
bouge(M,1,4)
 
ans =
 
    10     5     6     0
     3     1     4     2
     8    11    13    14
    10     9     7    15

**Jean Dumoncel** · 27/04/2012, 15h36

Yep, tu es sûr de bien utiliser le code que tu nous montres?

**ol9245** · 27/04/2012, 15h50

Ca marche aussi chez moi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
>>  M = [  0    10     5     6;
     3     1     4     2;
     8    11    13    14;
    10     9     7    15] 
 
M =
 
     0    10     5     6
     3     1     4     2
     8    11    13    14
    10     9     7    15
 
>> bouge(M,1,4)
    10     5     6     0
     3     1     4     2
     8    11    13    14
    10     9     7    15
 
 
ans =
 
    10     5     6     0
     3     1     4     2
     8    11    13    14
    10     9     7    15

Ceci dit, je ne trouves pas que cette fonction soit très utile. J'aurais pour ma part programmé uniquement les déplacements d'une case à la fois et pour cela, j'aurais donné les directions : haut bas droite et gauche.

Tu as ensuite besoin d'un générateur de coup : soit une position donnée, quels sont les coups disponibles (il y en a entre 2 -dans les coins- et 4 -au milieu du tableau-)

Il te faut ensuite une mesure de la distance au but. c'est une mesure que tu vas chercher à minimiser progressivement. Ca peut être par exemple la somme des distances de chaque case à sa position finale.

Puis tu explore l'arbre des possibilités sur un nombre n de coups (n ~ 10) que tu choisis et tu prends le chemin qui minimise la distance au bout de n coups.

Il y a peut-être des stratégies plus fines spécialement pour ce jeu là mais je ne les connais pas. Ce que je te décris ici c'est une stratégie générale.

**Wardock** · 27/04/2012, 18h39

Merci à tous !

ol9245, ta stratégie ne fonctionne pas parce que sur un taquin, si le vide n'est pas juxtaposé à la case que tu veux bouger, tu ne peux rien faire !

Et oui, je suis sûr à 100% d'utiliser cette fonction, puisque c'est la seule qui se trouve dans le workspace.. : / Je n'y comprends rien, un bug qqpart éventuellement ?

En tout cas merci de votre aide, il faut que j'essaye sur un autre poste maintenant..

Invité · 27/04/2012, 19h04

Dans ton premier message, c'est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function Z=bouge(M,lb,cb);

alors que dans ton deuxième

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Bouge2(M,1,4)

c'est normal ?

**ol9245** · 27/04/2012, 19h04

Envoyé par Wardock

Merci à tous !

ol9245, ta stratégie ne fonctionne pas parce que sur un taquin, si le vide n'est pas juxtaposé à la case que tu veux bouger, tu ne peux rien faire !

Et oui, je suis sûr à 100% d'utiliser cette fonction, puisque c'est la seule qui se trouve dans le workspace.. : / Je n'y comprends rien, un bug qqpart éventuellement ?

En tout cas merci de votre aide, il faut que j'essaye sur un autre poste maintenant..

Je n'ai pas du me faire comprendre.
Pour boucher un vide, tu peux le remplir avec la case du dessus, du dessous, de droite ou de gauche. Ca te fait 4 coups possibles au mieux.

Ta fonction, je veux dire que je n'aurais pas abordé le problème de cette manière. Tu te casses les pieds à programmer des coups multiples alors qu'il te suffit d'une fonction qui te programme les 4 coups élémentaires. Pour un coup multiple, tu enchaine plusieurs coups élémentaires et c'est fini.

Une bonne méthode de programmation (la mienne) décrite ci-dessous :
si au bout de 2 heures j'ai pas réussi à débugger un bout de code, je mets tout à la poubelle, je vais prendre l'air, et je reviens travailler sur une page blanche.

Là, comme je t'écris, ça fait 2 semaines que je suis sur le même programme. je l'ai réécrit je sais pas combien de fois à partir d'une page blanche et finalement, ce matin, ça a marché. Un code qui veut pas céder, c'est pas un bon code. C'est de la bouillie pour chat malade et c'est bon pour la poubelle.

Si cette méthode de travail marche pour moi, elle doit aussi marcher pour toi

**Wardock** · 27/04/2012, 19h13

Winjerome, c'est normal : le programme se nomme Bouge2.m, la fonction est donc appelée à ce titre.. Je n'ai pas l'impression que ça ait changé quelque chose au problème.

Ol9245, tu sais quoi, je vais tester ton truc. Mais j'ai l'impression que mon code est bon, quand même ! x] RDV demain pour plus d'aventures

Merci à vous 2.
Vous êtes comme ça

**Jean Dumoncel** · 27/04/2012, 19h28

Es-tu sûr que c'est la seule dans le workspce?
Que renvoie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

which -all Bouge2

?

Sinon Matlab possède des outils de debuggage très performant : les points d'arrêt (breakpoint) qui permettent de t'arrêter à l'intérieur d'un programme pour pouvoir entre autre vérifier les valeurs intermédiaires de tes variables. Places des points d'arrêt sur certaines lignes de ton programme et vérifie que tout s'exécute comme tu le voudrais.

**Wardock** · 29/04/2012, 16h08

Envoyé par magelan

Que renvoie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

which -all Bouge2

?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
>> which -all Bouge2
C:\Documents and Settings\Administrateur\Bureau\ProjetIRI5\Bouge2.m

... Tout paraît en ordre, pourtant, j'ai toujours ces E@ncàç$% déplacements parasites, notamment pour passer de M(1,4) à M(1,1). C'est le désespoir !

Tant pis, je finirai chômeur... :C

**ol9245** · 08/05/2012, 23h10

Ou en es-tu ?
J'ai commencé à programmer ton jeu de taquin parce que ça m’amuse et je sais comment ce genre de truc se programme, mais le temps dont je dispose pour m’amuser est limité, et le boulot quand même assez significatif (je ne code plus aussi vite qu'il y a 30 ans

).

Problème un peu "Taquin"

MATLAB

Discussions similaires

Partager

Partager