technique du backtracking

**programmation_** · 09/12/2013, 01h13

Bonjour,

débutant en c++ je ne sais pas comment résoudre un problème intitulé drôle de zèbre par la méthode du backtracking, voila le sujet:

Cinq maisons de couleurs différentes sont habitées par des hommes de nationalités diverses, ayant chacun son animal favori, sa boisson préférée et sa marque de cigarettes. Ces cinq maisons respectent les contraintes suivantes :
– L'Anglais habite la maison rouge.
– Le chien appartient à l'Espagnol.
– On boit du café dans la maison verte.
– L'Ukrainien boit du thé.
– La maison verte est à côté de la blanche, à droite.
– Le fumeur de Old Gold élève des escargots.
– On fume des Kool dans la maison jaune.
– On boit du lait dans la maison du milieu.
– Le Norvégien habite la première maison à gauche.
– Le fumeur de Chesterfield habite à côté du propriétaire du renard.
– Le fumeur de Kool habite à côté du propriétaire du cheval.
– Le fumeur de gitanes boit du vin.
– Le Japonais fume des Craven.
– Le Norvégien habite à côté de la maison bleue.

Pour ce problème des structures légères suffiront : une matrice 5x5 (d'entiers ou de caractères par exemple) contiendra les 5 caractéristiques des 5 maisons.

J'ai crée une fonction valide qui vérifie toutes les contraintes:

Code :

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

1
2
3
4
5
enum couleur {rouge, blanche, bleue, jaune, verte};
enum nationalite {anglais, espagnol,ukrainien, norvegien, japonais};
enum animal {chien, escargot, renard, cheval, zebre};
enum boisson {cafe, the, lait, vin, eau};
enum cigarette { oldgold, kool, craven, chesterfield, gitane};

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
46
47
48
49
50
51
52
bool valide( int maison[5][5], int i ,int a )
{
 
//sur une même ligne: les valeurs doivent être différentes
  for(int k=0;k<i;k++)
   {
 
       if(maison[a][i]==maison[a][k]) return false;
   }
 
	//– L'Anglais habite la maison rouge
	if( !(maison[1][i]==0 && maison[0][i]==0) ) return false ;
 
	//– Le chien appartient à l'Espagnol.
	if( !(maison[2][i]==0 && maison[1][i]==1) ) return false ;
 
	//– On boit du café dans la maison verte.
	if( !(maison[3][i]==0 && maison[0][i]==4) ) return false  ;
 
	//– L'Ukrainien boit du thé.
	if( !(maison[1][i]==2 && maison[3][i]==1) ) return false;
 
	//– La maison verte est à côté de la blanche, à droite.
	if( !(maison[0][i]==4 && maison[0][i+1]==1) ) return false ;
 
	//– Le fumeur de Old Gold élève des escargots.
	if( !(maison[4][i]==0 && maison[2][i]==1) ) return false;
 
	//– On fume des Kool dans la maison jaune.
	if( !(maison[4][i]==1 && maison[0][i]==3)  ) return false ;
 
	//– Le fumeur de Chesterfield habite à côté du propriétaire du renard.
	if( !(maison[4][i]==3 && (maison[2][i+1]==2 || maison[2][i-1])==2 )) return false;
 
	//– Le fumeur de Kool habite à côté du propriétaire du cheval.
	if( !(maison[4][i]==1 && ( maison[2][i+1]==3 || maison[2][i-1]==3) )) return false;
 
	//– Le fumeur de gitanes boit du vin.
	if( !(maison[4][i]==4 && maison[3][i]==3 )) return false ;
 
	//– Le Japonais fume des Craven.
	if( !(maison[4][i]==2 && maison[1][i]==4 ) ) return false;
 
	//– Le Norvégien habite à côté de la maison bleue.
	if( !((maison[1][i]==3 && (maison[0][i+1]==2)) )) return false ;
 
 
 
	else return true;
 
 
}

j'ai crée une fonction affiche qui visualise toute la matrice, une fonction estVide qui permet de vérifier s'il y a une case à -1 et une fonction chercher où se passe le backtracking qui malheureusement ne fonctionne pas vraiment:

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
void chercher(int M[5][5], int j, int I)
{
 
    if (estVide(M))
        affiche(M);
    else
    {
        for ( int i = 0 ; i < 5 ; i++)
        {
            M[j][I]=i;
            if (valide(M,j,I))
                chercher(M, j+1 ,I+1);
        }
 
  }
}

La matrice est initialisé à -1 avec :

Code :

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

1
2
3
4
5
6
7
8
9
 
   //On boit du lait dans la maison du milieu.
    maison[3][2]=2;
 
    //Le Norvégien habite la première maison à gauche.
     maison[1][0]=3;
 
   // Le Norvégien habite à côté de la maison bleue.
   maison[0][1]=2;

la fonction chercher n'affiche rien j'ai l'impression qu'elle ne parcourt pas tous les chemins possibles.

Je vous remercie pour toute éventuelle aide.

**Bousk** · 09/12/2013, 11h21

Salut,

ça me rapelle les jeux des anciens mickey parade

As-tu déjà réussi à répondre à ton problème sur un simple papier ?
Avant de vouloir algorithmer tout ça, c'est un début.

Un tableau te permet de voir directement où tu en es et de matcher le tout

Attention à ton utilisation des tableaux, ça m'a l'air de foncer droit dans le mur chercher(M, j+1 ,I+1);