fonction recursive qui donne boucle infini
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
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
voici le code.
Code:
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.
fonction recursive pour la configuration du jeu futoshiki
j'ai modifie la condition d'arret mais ma fonction n'affiche pas la configuration juste.
voila ma fonction modifiee
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
|
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
