c++ - 使用 pthread 解决 N 个皇后难题

Question

我知道如何使用回溯和递归来解决 n 个皇后难题。

我在想如何使用多线程来优化它。

我正在尝试使用 p 线程。

基本上我无法理解 top 在哪里应用线程，以及在哪里加入线程。

由于这是递归，我也无法理解线程在这里如何工作。

--

谢谢

阿洛克 Kr.

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

您可以针对不同的算法对其进行修改