[Problème] Programme huit reines

**thegreatbato** · 04/05/2006, 16h14

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** · 04/05/2006, 16h28

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** · 04/05/2006, 16h41

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.

**fearyourself** · 04/05/2006, 16h42

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

**Eusebius** · 04/05/2006, 16h44

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

**larnicebafteur** · 04/05/2006, 16h45

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** · 04/05/2006, 16h45

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** · 04/05/2006, 16h50

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

**FidoDido®** · 04/05/2006, 16h51

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’

**thegreatbato** · 04/05/2006, 16h53

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** · 04/05/2006, 16h57

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

**gege2061** · 04/05/2006, 16h58

Envoyé par 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 ?

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.

**Eusebius** · 04/05/2006, 16h59

Envoyé par Trap D

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

Est-ce que les tableaux ne sont pas toujours passés par adresse ?

**thegreatbato** · 04/05/2006, 17h06

Le programme a la base était avec des variables globales, je me suis arrangé pour qu'il n'y en ait plus, donc en passant ces variables dans les arguments des fonctions, le problème serait donc parce que l'empilement est beaucoup plus important que sur le problème que j'ai trouvé...

Est ce que l'emploi de variables globales pourrait règler le problème ?

**gege2061** · 04/05/2006, 17h18

Envoyé par thegreatbato

Est ce que l'emploi de variables globales pourrait règler le problème ?

Oui mais c'est pas très propre, tu peux passer un pointeur sur une structure de données :

Code :

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

1
2
3
4
5
6
7
struct param
{
  int numligne;
  int point[8][8];
  int ligne[8];
  int e[8];
};

ce qui donne :

Code :

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

void placedame (struct param *p);

**fearyourself** · 04/05/2006, 17h37

Le problème est une erreur dans un test:

Code :

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

        if (a + x < 8 && b + x >= 0)

Mais maintenant ça boucle...

Jc

**Emmanuel Delahaye** · 04/05/2006, 19h24

Envoyé par Eusebius

Est-ce que les tableaux ne sont pas toujours passés par adresse ?

Non. En C tout est passé par valeur. Pour le tableau, on passe une valeur qui est l'adresse du premier élément. Il faut un paramètre de plus pour la taille...

**Emmanuel Delahaye** · 04/05/2006, 19h29

Envoyé par thegreatbato

Le programme a la base était avec des variables globales, je me suis arrangé pour qu'il n'y en ait plus, donc en passant ces variables dans les arguments des fonctions, le problème serait donc parce que l'empilement est beaucoup plus important que sur le problème que j'ai trouvé...

Ben oui il faut faire, disons, intelligement, c'est à dire en organisant tes donnée en structures et en passant l'adresse de la structure.

**Eusebius** · 04/05/2006, 20h29

Envoyé par Emmanuel Delahaye

Non. En C tout est passé par valeur. Pour le tableau, on passe une valeur qui est l'adresse du premier élément. Il faut un paramètre de plus pour la taille...

Tu chipotes quand même ! C'est un passage par valeur d'une adresse... L'idée c'est quand même qu'on duplique pas le tableau pour un passage de paramètre.

**thegreatbato** · 04/05/2006, 20h38

Je suis vraiment perdu ! J'en peut plus d'analyser ce code dans tous les sens !

[Problème] Programme huit reines

C

Discussions similaires

Partager

Partager