使用pthreads解決N皇后拼圖

Question

我知道如何解決n皇后拼圖，使用回溯和遞歸。

我在想如何使用多線程來優化它。

我想用p - 線程。

基本上我無法理解頂端應用線程的位置，以及在哪裏加入線程。

由於這是遞歸，我也無法理解線程在這裏如何工作。

-

感謝

阿洛克氪。

Answer 1

一種方法是使用隊列將每個擴展放入隊列中，而不是進行遞歸。有一個流行的擴展和它的工作線程池：

create a state with an empty board and put it into the queue 
create N threads with the following function 

線程函數：

while not done: 
    1) pop a state S from the queue (use locks), if queue is empty, 
    wait on a semaphore until there is an S 
    2) expand state S 
    2a) if S has feasible children then put them into the queue 
     except for one state SS, call it S and goto 2 
    (also signal the semaphore) 
    2b) if S has no feasible children goto 1 
end while 

您可以修改此不同的算法