Chinaunix

标题: 请教算法问题，如何使N皇后算法支持多线程? [打印本页]

---

作者: soichiro    时间: 2006-04-12 21:46
标题: 请教算法问题，如何使N皇后算法支持多线程?
我现在用以下代码计算16皇后问题，但在多路CPU的机器上其实只使用了一个CPU，所以要使用线程来加快计算速度，我现在只知道N皇后算法其实可以看做是棋盘的第一列的每一空都先放置一个皇后，总共是N种放置位置，然后再对其它列的空逐一检测，所以理论上可以分给多个线程独立运算，但我具体不清楚怎么做。

1. 
   
2. #include <stdio.h>
   
3. #define N 16
   
4. 
   
5. int a[N+1], b[2*N], c[2*N+1];
   
6. 
   
7. int count;
   
8. 
   
9. void queen(int i)
   
10. {
    
11.   int j;
    
12.   
    
13.   for(j=1; j<=N; j++)
    
14.     {
    
15.       if(a[j] + b[i+j] + c[i-j+N] == 3)
    
16.         {
    
17.           a[j] = 0; b[i+j] = 0; c[i-j+N] = 0;
    
18.           
    
19.           if(i < N)
    
20.             queen(i+1);
    
21.           else
    
22.             count++;
    
23.           
    
24.           a[j] = 1; b[i+j] = 1; c[i-j+N] = 1;
    
25.         }
    
26.     }
    
27. }
    
28. 
    
29. int main()
    
30. {  
    
31.   int i;
    
32. 
    
33.   for(i=0; i<=N; i++) a[i]=1;
    
34.   for(i=0; i<=2*N; i++) b[i]=1;
    
35.   for(i=0; i<=2*N-1; i++) c[i]=1;
    
36.   
    
37.   queen(1);
    
38. 
    
39.   printf("%d\n", count);
    
40. 
    
41.   return 0;
    
42. }
    

复制代码

如果用:

1. pthread_create (&thread, NULL, &thread_function, NULL);

复制代码

产生4个线程来计算，请问要如何修改上面的算法程序？谢谢！

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2