Discussion :

[simpatico]

Dans le cadre d'un compte rendu je dois ecrire un programme en langage C qui donnee la configuration initiale du jeu japonais Futoshiki, resoud le jeux en affichant la configuration finale.
futoshiki est un puzzle japonais dans lequel une matrice carre n.n doit etre remplie par les chiffres de 1 a n respectant les deux regles suivantes.
-sur chaque ligne et chaque colonne il ne doit pas y avoir une repetition de aucun numero.
-si entre deux cases adjacentes il y a un signe d'inegalite, ce signe doit etre respecte.
voila un exemple.

fichier IN:

5
0 | 0 | 0 | 0 | 0
- - - - v - - - -
0 > 0 | 0 | 0 | 3
- - - - - - - - -
0 | 0 < 2 | 0 | 0
- - - - v - - - -
0 | 0 | 0 | 0 | 4
^ - ^ - - - - - - 
0 | 0 | 0 | 0 | 0

fichier out

5
1 | 4 | 5 | 3 | 2
- - - - v - - - -
5 > 2 | 4 | 1 | 3
- - - - - - - - -
3 | 1 < 2 | 4 | 5
- - - - v - - - -
2 | 3 | 1 | 5 | 4
^ - ^ - - - - - - 
4 | 5 | 3 | 2 | 1

j'ai resolu tout mais quand je fais une fonction recursive pour trouver la solution ca me donne une boucle infinie je ne sais pas prk.
voici le code.

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
int trovare_soluzione(shiki ** t, int n, int f)
{
    int i, j, r;
    int s = n / 2 + 1;
    if (f == 0)
	return (configuration_check(t, n));
    for (i = 0; i <= n; i++) {
	for (j = 0; j <= n; j++) {
	    if (isdigit(t[i][j].num) && t[i][j].flag == -1) {
		for (r = 1; r <= s; r++) {
		    t[i][j].num = r + '0';
		    t[i][j].flag = 1;
		    if (trovare_soluzione(t, n, f - 1) == 1) {
			return (1);
		    }
//backtrack
		    t[i][j].flag = -1;
		}
	    }
	}
    }
    return 0;
}

shiki est une structure de donnees qui contient deux champs. le champs num pour memoriser les caracteres lits du fichier in ( a l'exception des tabulations) et un champ flag ( se flag=-1 veut dire que qu'on doit inserer un num se flag=1 ca veut dire que le numero a ete deja trouve)
la fonction configuration_check est une focntion qui verifie a chaque fois si les regles du jeu sont respectes elle retourne 1 si elles sont respectees 0 sinon.

merci d'avance de votre aide.

[Bktero]

Si boucle infinie, alors ta condition d'arrêt de récursivité n'est jamais vraie.

[souviron34]

ta boucle est infinie parce que tu rappelles la fonction DANS la boucle..

Il faut que tu mettes un flag qui indique que tu dois rappeler et que tu sortes des boucles..

[simpatico]

je crois que la condition darret est juste.
Mr Souviron est ce que vous expliquer plus en details, ou dois+je introduire les flags? merci bcp pour vos reponses

[souviron34]

je ne sais pas ce que tu veux faire, mais quand tu fais :

Code C :

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

1
2
3
4
5
6
7
8
9
    for (i = 0; i <= n; i++) {
	for (j = 0; j <= n; j++) {
	    if (isdigit(t[i][j].num) && t[i][j].flag == -1) {
		for (r = 1; r <= s; r++) {
		    t[i][j].num = r + '0';
		    t[i][j].flag = 1;
		    if (trovare_soluzione(t, n, f - 1) == 1) {
			return (1);
		    }

• Si ta fonction ne retourne pas 1, tu boucles sur tous les i, tous les j, tous les r
  
  
• Si ta fonction retourne 1, tu continues à boucler sur les i et j suivants à l'étape du dessus
  
  
• Enfin, on ne sait pas avec quoi tu as initilaisé, et tu testes en entrée de boucle avec -1 : es-tu sûr d'avoir initialisé tout à -1 ??

[simpatico]

j'ai modifie la condition d'arret mais ma fonction n'affiche pas la configuration juste.
voila ma fonction modifiee

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
 
int trovare_soluzione(shiki **t, int riga, int colonna,int n){
int i,k,j,trovato=0,s;
s=n/2+1;
if(riga==n && colonna==n ){// condition d'arret apres avoir parcouru toute la matrice je verifie si la conifguration exacte respectes les regles
if(configuration_check(t,n)==1)
return 1;
else return 0;
}
if(t[riga][colonna].num=='0'){// je controle si l'element est egale a 0 donc je dois inserer un numero different de 0;
trovato=0;
for(i=1;i<=s;i++){  // les valeurs possibles a inserer
for(k=0;k<=n;k++){
if(isdigit(t[riga][k].num) && t[riga][k].flag==1 &&k!=colonna){
if(t[riga][k].num==i+'0')  // je controle si la valeur a inserer ne se trouve pas deja dans la ligne
trovato=1;
}}
if(trovato==0){
for(j=0;j<=n;j++){
if(isdigit(t[j][colonna].num) && t[j][colonna].flag==1 &&j!=riga){
if(t[j][colonna].num==i+'0') // je controle si la valeur a inserer ne se trouve pas deja dans la colonne
trovato=1;
}}
if(trovato==0){  // si je ne le trouve pas j'insere un numero
t[riga][colonna].flag=1;
t[riga][colonna].num=i+'0';
colonna++; // j'incremente le num de colonne
if(colonna==n){ 
    riga++;
    colonna=0;}
    if(trovare_soluzione(t,riga,colonna,n))return 1;// j'appelle ma methode recursive
    //backtrack
    t[riga][colonna].flag=-1;
t[riga][colonna].num='0';
}}}}
return 0;
 
}

merci d'avance de votre aide

[souviron34]

Déjà un formatage s'impose, c'est illisible...

Code C :

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
int trovare_soluzione (shiki **t, int riga, int colonna,int n)
{
int i,k,j,trovato=0,s;
 
s=n/2+1;
if ( riga==0 && colonna==0 )
  {
     // condition d'arret apres avoir parcouru toute la matrice je verifie si la conifguration exacte respectes les regles
     if ( configuration_check(t,n)==1 )
         return 1;
     else 
         return 0;
  }
 
if ( t[riga][colonna].num=='0' )
  {
     // je controle si l'element est egale a 0 donc je dois inserer un numero different de 0;
     trovato=0;
     for ( i=1 ; i<=s; i++)
       {
         // les valeurs possibles a inserer
         for ( k=0; k<=n; k++ )
           {
              if ( isdigit(t[riga][k].num) && t[riga][k].flag==1 && k!=colonna )
               {
                   if ( t[riga][k].num==i+'0' )  // je controle si la valeur a inserer ne se trouve pas deja dans la ligne
                     trovato=1;
               }
           }
 
         if ( trovato==0 )
          {
             for ( j=0; j<=n; j++ )
               {
                 if ( isdigit(t[j][colonna].num) && t[j][colonna].flag==1 && j!=riga )
                  {
                     if ( t[j][colonna].num==i+'0' ) // je controle si la valeur a inserer ne se trouve pas deja dans la colonne
                       trovato=1;
                   }
               }
 
             if ( trovato==0 )
              { 
                  // si je ne le trouve pas j'insere un numero
                  t[riga][colonna].flag=1;
                  t[riga][colonna].num=i+'0';
                  colonna++; // j'incremente le num de colonne
 
                  if ( colonna==n )
                   { 
                      riga++;
                      colonna=0;
                   }
 
                  if ( trovare_soluzione(t,riga,colonna,n) )
                    return 1;// j'appelle ma methode recursive
 
                  //backtrack
                  t[riga][colonna].flag=-1;
                  t[riga][colonna].num='0';
               }
           }
        }
    }
 
return 0;
}

Maintenant, est-ce ça que tu veux ?


D'autre part, dans la ligne :

Code :

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

if ( riga==0 && colonna==0 )

toi tu as mis le caractère o et non pas 0 ..

[anacharsis]

j'y ai pensé tout de suite en lisant le premier post, puis ...
mais pourquoi vouloir écrire une fonction récursive pour une situation aussi simpliste (futoshiki, sudoku ...) : une douzaine d'états et très peu de contraintes. c'est un problème des 8 reines (un peu plus lourd) qui peut être résolu en une centaine de lignes.
le seul avantage que je trouve à une écriture récursive est la facilité de (re)lecture quand les conditions de retour sont claires.

A+