technique du backtracking
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:
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:
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:
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:
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.
