Discussion :

[thegreatbato]

Bonjour ! Voila j'ai un problème pour un programme qui cherche toutes les combinaisons possibles du problème des huit reines (placer 8 reines sur un echiquier de 8*8 sans qu'aucune ne puisse manger une autre).

J'appelle une fonction placedame(...) et elle se déroule a mon avis normalement, puis tout d'un coup le programme plante sans aucun affichage d'erreur ...

Je devais utiliser les listes chaînées et la récursivité.

C'est assez urgent je dois remettre le projet demain donc si vous pouviez m'aider assez vite ça serait gentil !

"echiq.h"

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
typedef struct
        {
               int tab_dames[8][8];
               struct echiq *prec;
               struct echiq *suiv;
        } echiq;
 
typedef struct
        {
               echiq* premier;
               echiq* dernier;
        } pointeur;
 
void Ajout(pointeur *l, int dames[8][8]);
void Init(pointeur *l);
void dame(int a,int b,int num, int point[8][8]);
void placedame(int numligne, int point[8][8],  int ligne[8], int e[8]);

"reines.c"

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include "echiq.h"
 
int x,y;        // variables pour les boucles de l'affichage du tableau
 
void Init(pointeur *l)
{
     l->premier = NULL;
     l->dernier = NULL;
}
 
void Ajout(pointeur *l, int dames[8][8])
{
   int i,j;
   echiq *nouv = malloc(sizeof(echiq));
   if(!nouv) return;
   for(i=0;i<8;i++)
   {
        for(j=0;j<8;j++)
        {
             nouv->tab_dames[i][j] = dames[i][j];
        }
   }
   nouv->prec = l->dernier;
   nouv->suiv = NULL;
   if(l->dernier) l->dernier->suiv = nouv;
   else l->premier = nouv;
   l->dernier = nouv;
}
 
void placedame(int numligne, int point[8][8],  int ligne[8], int e[8])
{
    for (ligne[numligne] = e[numligne]; ligne[numligne] < 8; ligne[numligne]++)
    {
        if (point[ligne[numligne]][numligne] == 0)
        {
            e[numligne] = ligne[numligne] + 1;
            dame(numligne, ligne[numligne], 2, point);
            if (numligne < 7)
            {
                placedame(numligne+1, point, ligne, e);
            }
            if (numligne == 7)
            {
                dame(numligne, ligne[numligne], -2, point);
                dame(numligne-1, ligne[numligne-1], -2, point);
                placedame(numligne-1, point, ligne, e);
            }
        }
    }
    if (numligne !=0)
    {
        if (ligne[numligne] >= 8)
        {
            for (x=numligne; x < 8; x++)
            {
                e[x]=0;
            }
            dame(numligne-1, ligne[numligne-1], -2, point);
            placedame(numligne - 1, point, ligne, e);
        }
    }
}
 
 
void dame(int a,int b,int num, int point[8][8])
{
    for (x=0; x < 8; x++)
    {
        if (x != a)
        {
            point[b][x] += num;
        }
        if (x !=b)
        {
            point[x][a] += num;
        }
    }
    for (x=1; x < 8; x++)
    {
        if (a + x < 8 && b + x < 8)
        {
            point[b+x][a+x] += num;
        }
        if (a - x >= 0 && b - x >= 0)
        {
            point[b-x][a-x] += num;
        }
        if (a - x >= 0 && b + x < 8)
        {
            point[b+x][a-x] += num;
        }
        if (a + x < 8 && b + x >= 0)
        {
            point[b-x][a+x] += num;
        }
    }
    if (num > 0)
    {
        point[b][a] += 1;
    }
    if (num < 0)
    {
        point[b][a] -= 1;
     }
}
 
void main(void)
{
    int amorce[8], ligne[8];
    int i,j,k;
    int point[8][8];
    for(i = 0; i < 8; i++)
    {
        amorce[i] = 0;
        ligne[i] = 0;
    }
    pointeur ListEchiq;
    Init(&ListEchiq);
    for(i = 0; i < 92; i++)
    {
        for(j = 0; j < 8; j++)
        {
            for(k = 0; k < 8; k++)
            {
                point[j][k] = 0;
            }
            amorce[j] = 0;
        }
        placedame(0, point, ligne, amorce);
        for(j = 0; j < 8; j++)
        {
            for(k = 0; k < 8; k++)
            {
                printf("%d  ", point[j][k]);
            }
            printf("\n");
        }
        Ajout(&ListEchiq, point);
    }
 
}

Merci beaucoup !

[Trap D]

Désolé, mais présenté comme ça, on n'a absolument pas envie de t'aider, en plus ton code est beaucoup trop commenté ...
Qu'est-ce qui coince, tu as un segfault, il ne te rend rien ????
Au boulot, si tu veux qu'on t'aide, aide-nous !

[thegreatbato]

Bon dans le main j'appelle la fonction placedame ... Il ne fait aucune erreur, il bloque juste après la 31730 récursive ... bizzare non ?

La fonction dame(...) permet de placer ou retirer une dame.

La fonction placedame(...) permet d'essayer les positions possibles.

C'est a peu près tout ce que j'ai compris, j'ai eu le code que j'ai modifié pour qu'il n'ai plus de variables globales, pour qu'il fonctionne en C et que les solutions soient représentées dans des listes chaînées.

[Eusebius]

faire débugger par quelqu'un d'autre un code que tu ne comprends pas... le panard !

[FidoDido®]

Déjà ton code renvoie quelques warnings :

reines.c: In function ‘Ajout’:
reines.c:15: warning: implicit declaration of function ‘malloc’
reines.c:15: warning: incompatible implicit declaration of built-in function ‘malloc’
reines.c:24: warning: assignment from incompatible pointer type
reines.c:26: warning: assignment from incompatible pointer type
reines.c: At top level:
reines.c:109: warning: return type of ‘main’ is not ‘int’

[larnicebafteur]

Pourquoi ne pas essayer de simplifier le problème, avec un echiquier de taille 4*4 (pas de solutions en dessous, je crois). Le code semble pouvoir se simplifier facilement pour ceci ...

Ensuite, il sera plus simple de voir ce qui s'y passe au niveau debogage.

[Trap D]

T'as pas l'impression que t'as peut-être pété la pile d'exécution par hasard ????
Recopier des codes sans rien comprendre quel intérêt ?

[fearyourself]

Ok plus sérieusement, la récursive devrait marcher pour 8*8, j'ai fait un jour ce problème et la récursive ne suit plus lorsqu'on passe à 11 ou 12...

Par contre, ta programmation est dangereuse, lorsqu'on fait une récursive, on fait ceci:

Code :

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

1
2
3
4
5
 
Fonction récursive:
Gestion des entrées erreurs: si c'est le cas, on sort en disant : ERREUR
Gestion des valeurs d'arrêt: si c'est le cas, on sort rendant un résultat si nécessaire
Fonction récursive générale

Je ne vois pas cela dans ton code donc c'est normal que la récursive peut planter...
Jc

[thegreatbato]

J'ai quand même compris la majeure partie, mais je n'arrive pas a comprendre d'ou vient le problème ! Peut être la pile d'exécution effectivement ! Le code était en C++ a la base, est-ce peut être le problème aussi ? ça m'étonnerai parce que toutes les fonctions que j'utilise sont connues par le C aussi.

Ce qui m'étonne aussi c'est que dans la récursive il n'y ai pas de condition d'arrêt ... peut être là le problème ?

Apparemment il y a une erreur de segmentation

[Trap D]

Sauf qu'il faut regarder la taille des arguments passés, passe des pointeurs, pas tous les tableaux en entier....

[gege2061]

Bon dans le main j'appelle la fonction placedame ... Il ne fait aucune erreur, il bloque juste après la 31730 récursive ... bizzare non ?

Bizzare ? Non ! A chaque appel de fonction, il y a empilement des paramètres sur la pile (16 octects par appel à la fonction placedame sur ma machine), ce qui fait au bout de 31730 appels : 0.5 Mo d'empilé ! La pile n'est pas une zone mémoire infinie, c'est le problème avec la récursion, hélas le problème des dames est difficilement solvable sans récursion.

Donc diminue le nombres et la taille des paramètres de la fonction récursive et aussi le nombre d'appel.

Note : mes remarques sont valables que si le programme est code correcte bien sûr.

[fearyourself]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <unistd.h>
#include <stdio.h>
 
int main()
{
printf("Calcul des positions\n");
sleep(3);
printf("Le nombre de solutions au problème des 8 reines est: 92\n");
printf("Mais seulement 23 uniques, les autres sont des rotations\n");
return 0;
}

A mon avis, si ton prof voit la 2ème ligne il sera bluffé...


Plus sérieusement,

1) Faudrait en dire un peu plus

2) Fallait s'y prendre un peu en avance, non?
Jc