Discussion :

[Denar]

Bonjour à tous,

J'ai un petit problème sur lequel je bosse depuis quelques jours, et j'ai l'impression qu'il y a quelque chose que je ne dois pas comprendre au niveau de la gestion des threads.

J'ai fait un programme pour résoudre le problème des 8 queens (mettre 8 reines sur un plateau d'échecs sans que 2 soient sur la même ligne/colonne ou diagonale). Le programme marche correctement de façon séquentielle et trouve les 92 solutions au problème.

Cependant, lorsque je crée un pool de 8 threads pour partager les calculs (en leur attribuant à chacun un placement particulier de la première reine sur la première ligne), je n'obtiens plus que 88 solutions.

Voici le programme :

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
# include<stdio.h>
# include <pthread.h>
 
# define Q  8
 
struct QPOINT {int x,y;};
 
int N;
pthread_mutex_t Nmutex;
 
void MoveQueen(int x, QPOINT* q);
 
bool checkAll(int x, QPOINT* q){
	for ( int i = x ; i > 0 ; i--)
	{
        for(int j = i - 1; j >= 0 ; j--)
        {
            if(q[i].x == q[j].x || q[i].y == q[j].y ||
                q[i].x + q[i].y == q[j].x + q[j].y ||
                q[i].x - q[j].x == q[i].y - q[j].y)
            {
                return false;
            }
        }
	}
    return true;
}
 
void* MoveQueenIni(void* i)
{
    QPOINT q[Q];
 
    q[0].x = 0;
    q[0].y = (int)i;
 
    MoveQueen(1, q);
}
 
void MoveQueen(int x, QPOINT* q){
 
	if(x >= Q)
	{
	    // Critical Section, protected by Nmutex
 
		pthread_mutex_lock(&Nmutex);
		printf("\n\nSolution : %d \n\n\t",++N);
		for(int j=0;j<Q;printf("\n\t"),j++)
		for(int i=0;i<Q;((q[j].x==j) && (q[j].y==i))?printf("Q%c",179) : printf("_%c",179),i++);
        pthread_mutex_unlock(&Nmutex);
		return;
	}
 
	for (int j = 0; j < Q ;q[x].x = x,j++){	q[x].y = j;
		  if(checkAll(x, q)) MoveQueen(x + 1, q);
	}
}
 
int main()
{
    pthread_t pool[Q];
 
    pthread_mutex_init(&Nmutex, NULL);
 
    // We divide the computations into 8 different threads
 
    for (int i = 0; i < Q; ++i)
    {
        pthread_create(&pool[i], NULL, MoveQueenIni, (void *)i);
 
        //MoveQueenIni((void*)i);      // Si je remplace la création des threads par cette ligne, j'obtiens bien les 88 solutions.
 
    }
 
    for(int i = 0; i < Q; ++i)
    {
          pthread_join(pool[i], NULL);
    }
 
}

Peut-être que j'ai raté quelque chose de simple dans la création des threads, mais je ne sais pas pourquoi il y a 4 solutions qui disparaissent.

Dans le main(), si je remplace la création des threads dans la boucle par un appel séquentiel direct à la fonction MoveQueenIni((void*)i); j'obtiens bien les 92 solutions attendues.

Merci de votre attention et toute aide ou piste est la bienvenue

[screetch]

ca m'a pris du temps de trouver ton bug...
ta manie de mettre des instructions a l'interieur du FOR est dangereuse.

tu as ecrit:

Code :

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

1
2
3
4
5
6
 
    for (int j = 0; j < Q; q[x].x = x, j++)
    {
        q[x].y = j;
        if(checkAll(x, q)) MoveQueen(x + 1, q);
    }

ce qui equivaut a:

Code :

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

1
2
3
4
5
6
7
8
 
    int j = 0;
    do
    {
        q[x].y = j;
        if(checkAll(x, q)) MoveQueen(x + 1, q);
        q[x].x = x, j++
    }while(j < Q);

lors de ton pre,ier passage dans la boucle, q[x].x n'est pas initialisé et il sera initialisé lors du deuxieme/troisieme/etc passage.

Code :

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

1
2
3
4
5
6
7
 
    for (int j = 0; j < Q; j++)
    {
        q[x].x = x;
        q[x].y = j;
        if(checkAll(x, q)) MoveQueen(x + 1, q);
    }

un code plus propre et qui marche...

(si ca marche en mode singlethread c'est purement du bol!)

[Denar]

Merci énormément, je vois que cette façon de présenter mes boucles est dangereuse et que c'est à cause de ça que j'ai commis cette erreur.

A l'avenir je vais garder mon code plus propre.

Merci de ton aide