Problème des 8 queens avec pThreads
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:
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 :)
