我有一个家庭作业要编写一个多线程数独求解器，它可以找到给定谜题的所有解决方案。我之前写过一个非常快速的单线程回溯数独求解器，所以我在数独求解方面不需要任何帮助。
我的问题可能与并非真正理解并发有关，但我看不出这个问题如何从多线程中受益。我不明白如何在不维护拼图的多个副本的情况下同时找到同一问题的不同解决方案。鉴于这个假设（请证明它是错误的），我看不出多线程解决方案如何比单线程更有效。
如果有人能给我一些关于算法的起始建议，我将不胜感激（请不要代码......）
我忘了提，要使用的线程数被指定为程序的参数，所以据我所知，它与拼图的状态没有任何关系......
此外，可能没有唯一的解决方案 - 有效的输入可能是一个完全空的板。我必须报告min(1000, number of solutions)并显示其中之一（如果存在）
真的很简单。基本概念是，在您的回溯解决方案中，您将在有选择时进行分支。您尝试了一个分支，回溯，然后尝试了另一种选择。
现在，为每个选择生成一个线程并同时尝试它们。如果系统中已有 < 一些线程（这将是您的输入参数），则仅生成一个新线程，否则只需使用简单的（即您现有的）单线程解决方案。为了提高效率，请从线程池中获取这些工作线程。
这在许多方面是一种分而治之的技术，您将选择作为一个机会，将搜索空间分成两半并将一半分配给每个线程。很可能一半比另一半更难，这意味着线程的生命周期会有所不同，但这就是使优化变得有趣的原因。
处理明显同步问题的简单方法是复制当前板状态并将其传递到函数的每个实例中，因此它是函数参数。这种复制意味着您不必担心任何共享并发。如果您的单线程解决方案使用全局变量或成员变量来存储板状态，则您将需要在堆栈上（简单）或每个线程（更难）上的副本。您需要返回的所有函数都是一个棋盘状态以及为达到该状态而采取的一些动作。
每个调用多个线程来完成工作的例程应该在有 n 个工作时调用 n-1 个线程，完成第 n 个工作，然后使用同步对象等待，直到所有其他线程完成。然后，您评估他们的结果 - 您有 n 个棋盘状态，返回移动次数最少的棋盘状态。
多线程在单个线程必须等待资源并且您可以同时运行另一个线程的任何情况下都很有用。这包括一个线程等待 I/O 请求或数据库访问，而另一个线程继续 CPU 工作。
如果各个线程可以分流到不同的 CPU（或内核），那么多线程也很有用，因为它们真正并发地运行，尽管它们通常必须共享数据，所以仍然会有一些争用。
我看不出多线程数独求解器比单线程数独求解器更高效的任何原因，仅仅是因为没有等待资源。一切都将在内存中完成。
但我记得我在 Uni 做的一些作业，它同样没用（Fortran 代码查看当你在 30 度一英里然后 15 度再挖一英里时隧道有多深 - 是的，我很漂亮老的 ：-）。关键是表明你可以做到，而不是它有用。
上算法。
我写了一个单线程求解器，它基本上在每次传递中运行一系列规则来尝试填充另一个正方形。一个示例规则是：如果第 1 行只有一个空方格，则该数字从第 1 行中的所有其他数字中显而易见。
所有行、所有列、所有 3x3 迷你网格都有类似的规则。还有检查行/列相交的规则（例如，如果给定的正方形由于行而只能包含 3 或 4，由于列只能包含 4 或 7，那么它是 4）。还有更复杂的规则我不会在这里详述，但它们基本上与您手动解决它的方式相同。
我怀疑您的实施中有类似的规则（因为除了蛮力之外，我想不出其他方法来解决它，如果您使用过蛮力，那么您就没有希望了:-)。
我建议将每个规则分配给一个线程并让它们共享网格。每个线程都会执行自己的规则，并且只有该规则。
更新：
乔恩，根据您的编辑：
[编辑] 我忘了提，要使用的线程数被指定为程序的参数，所以据我所知，它与拼图的状态没有任何关系......
此外，可能没有唯一的解决方案 - 有效的输入可能是一个完全空的板。我必须报告 min(1000, number of solutions) 并显示其中一个（如果存在）
看起来您的老师不希望您根据规则进行拆分，而是根据分叉点（可以应用多个规则）进行拆分。
我的意思是，在解决方案的任何时候，如果有两个或多个可能的前进，您应该将每个可能性分配给一个单独的线程（仍然使用您的规则来提高效率，但同时检查每个可能性）。这将为您提供更好的并发性（假设线程可以在单独的 CPU/内核上运行），因为不会有对板的争用；每个线程都会得到它自己的副本。
此外，由于您限制了线程数，因此您必须使用一些线程池魔法来实现这一点。
我建议的是有一个工作队列和 N 个线程。当您的主线程启动所有工作线程时，工作队列最初是空的。然后主线程将开始的拼图状态放入工作队列。
工作线程只是等待状态被放置在工作队列中，其中一个会抓取它进行处理。工作线程是您的单线程求解器，只需稍作修改：当有 X 个向前移动的可能性（X > 1）时，您的工作线程将其中的 X-1 个放回工作队列，然后继续处理另一种可能性。
所以，假设只有一种解决方案（真正的数独 :-)。第一个工作线程将在没有找到任何分叉的情况下减少解决方案，这与您当前的情况完全相同。
但是在第 27 步有两种可能性（例如，3 或 4 可以进入左上角的单元格），您的线程将创建另一个具有第一种可能性的棋盘（将 3 放入该单元格）并将其放入工作队列中。然后它将 4 放入自己的副本中并继续。
另一个线程将拿起该单元格中带有 3 的板并继续。这样，您就有两个线程同时运行以处理这两种可能性。
当任何线程决定其板不可解时，它会将其丢弃并返回工作队列以进行更多工作。
当任何线程决定其板已解决时，它会通知可以存储它的主线程，覆盖任何先前的解决方案（首先找到的是解决方案）或者如果它已经有解决方案则将其丢弃（最后找到的是解决方案）然后工作线程返回工作队列进行更多工作。在任何一种情况下，主线程都应该增加找到的解决方案的计数。
当所有线程都处于空闲状态并且工作队列为空时，main 要么会有解决方案，要么不会有解决方案。它还将有一个解决方案的计数。
请记住，工作线程和主线程之间的所有通信都需要互斥（我假设您根据问题中的信息知道这一点）。
多线程背后的想法是利用多个 CPU，允许您同时进行多个计算。当然，每个线程都需要自己的内存，但这通常不是问题。
大多数情况下，您想要做的是将可能的解决方案状态分成几个尽可能独立的子空间（以避免在线程创建开销上浪费太多资源），但“适合”您的算法（实际上受益从拥有多个线程）。
这是一个贪婪的蛮力单线程求解器：
如果您查看上面的大纲，步骤 2 和 3 的组合显然是多线程的候选者。更雄心勃勃的解决方案涉及创建递归探索，以生成提交到线程池的任务。
编辑回应这一点：“我不明白如何在不维护拼图的多个副本的情况下同时找到同一问题的不同解决方案。”
你不能。这就是重点。但是，一个具体的 9 线程示例可能会使好处更加明显：
可以想象，每个线程现在运行的问题空间稍小，每个线程都有可能在自己的 CPU 内核上运行。仅使用单线程算法，您无法获得多核机器的好处。
是的，基于回溯的数独求解器可以根据谜题从并行化中受益匪浅！拼图的搜索空间可以建模为树数据结构，并且回溯执行此树的深度优先搜索 (DFS)，这本质上是不可并行的。但是，通过将 DFS 与其相反形式的树遍历、广度优先搜索 (BFS)相结合，可以解锁并行性。这是因为 BFS 允许同时发现多个独立的子树，然后可以并行搜索。
因为 BFS 解锁了并行性，所以使用它保证使用全局线程安全队列，所有线程都可以将发现的子树推入/弹出该队列，与 DFS 相比，这需要显着的性能开销。因此，并行化这样的求解器需要微调执行的 BFS 的数量，以便执行足以确保树的遍历被充分并行化，但又不能过多地导致线程通信的开销（推送/弹出子树队列）超过了并行化提供的加速。
不久前，我并行化了一个基于回溯的数独求解器，并实现了 4 个不同的并行求解器变体以及一个顺序（单线程）求解器。并行变体都以不同方式和不同程度地结合了 DFS 和 BFS，最快的变体平均是单线程求解器的三倍以上（见底部图表）。
此外，为了回答您的问题，在我的实现中，每个线程都会收到初始拼图的副本（当线程产生时），因此所需的内存略高于顺序求解器 - 这在并行化某些东西时并不少见。但这就是您所说的唯一“低效率”：如上所述，如果 BFS 的数量经过适当微调，则通过并行化可实现的加速大大超过线程通信的并行开销以及更高的内存占用。此外，虽然我的求解器假设了独特的解决方案，但将它们扩展为处理不正确的谜题并找到所有解决方案将很简单，并且由于求解器设计的性质，不会显着降低加速比（如果有的话）。
数独求解器是否受益于多线程很大程度上取决于其底层算法。常见的方法，如约束传播（即基于规则的方法），其中难题被建模为约束满足问题或随机搜索，并没有真正受益，因为使用这些方法的单线程求解器已经非常快。然而，回溯在大多数情况下会受益匪浅（取决于谜题）。
您可能已经知道，数独的搜索空间可以建模为树数据结构：三级中的第一级表示第一个空单元格，第二级表示第二个空单元格，依此类推。在每个级别，节点代表给定其祖先节点值的该单元格的潜在值。因此搜索这个空间可以通过同时搜索独立的子树来并行化。单线程回溯求解器必须自己遍历整个树，一个接一个的子树，但并行求解器可以让每个线程并行搜索单独的子树。
有多种方法可以实现这一点，但它们都是基于深度优先搜索 (DFS) 和广度优先搜索 (BFS) 相结合的原理，这是树遍历的两种（相反）形式。单线程回溯求解器仅对整个搜索进行 DFS，这本质上是不可并行的。但是，通过将 BFS 添加到混合中，可以解锁并行性。这是因为 BFS 逐级遍历树（与 DFS 的逐个分支相反），从而在移动到下一个较低级别之前找到给定级别上的所有可能节点，而 DFS 获取第一个可能的节点并在移动到下一个可能的节点之前完全搜索其子树。因此，BFS 可以立即发现多个独立的子树，然后可以通过单独的线程进行搜索；DFS 没有
与多线程的情况一样，并行化代码很棘手，如果您不确切知道自己在做什么，最初的尝试通常会降低性能。在这种情况下，重要的是要意识到 BFS 比 DFS 慢得多，因此主要关注的是调整您执行的 DFS 和 BFS 的数量，以便执行足够的 BFS 以解锁发现多个子树的能力同时，还要最小化它，因此它的缓慢最终不会超过这种能力。请注意，BFS 本质上并不比 DFS 慢，只是线程需要访问发现的子树，以便它们可以搜索它们。因此，BFS 需要一个全局线程安全的数据结构（例如队列），子树可以由单独的线程推入/弹出该数据结构，与不需要线程之间任何通信的 DFS 相比，这需要显着的开销。因此，并行化这样的求解器是一个微调过程，并且希望执行足够的 BFS 来为所有线程提供足够的子树进行搜索（即在所有线程之间实现良好的负载平衡），同时最小化线程之间的通信（推/将子树弹出到队列中/从队列中弹出）。
不久前，我并行化了一个基于回溯的数独求解器，并实现了 4 个不同的并行求解器变体，并将它们与我也实现的顺序（单线程）求解器进行了基准测试。它们都是用 C++ 实现的。最佳（最快）并行变体的算法如下：
下图（取自我当时的报告）说明了这些步骤： 不同颜色的三角形代表不同的线程和它们遍历的子树。绿色节点表示该级别上允许的单元格值。注意在搜索深度执行的单个 BFS；在这一层发现的子树（黄色、紫色和红色）被推入全局队列，然后并行独立地遍历到树的最后一层（最后一个空单元格）。
如您所见，此实现仅执行一个级别（在搜索深度）的 BFS。这个搜索深度是可调的，优化它代表了前面提到的微调过程。搜索深度越深，执行的 BFS 就越多，因为树的宽度（给定级别上的 # 个节点）自然会增加您越往下走。有趣的是，最佳搜索深度通常处于相当浅的级别（即树中不是很深的级别）；这表明即使执行少量的 BFS 也足以生成充足的子树并在所有线程之间提供良好的负载平衡。
此外，由于全局队列，可以选择任意数量的线程。将线程数设置为等于硬件线程数（即 # 逻辑核心）通常是一个好主意；选择更通常不会进一步提高性能。此外，还可以通过执行树的第一级（第一个空单元格）的 BFS 来并行化在开始时执行的初始 DFS：然后并行遍历在级别 1 发现的子树，每个线程在给定搜索深度。这就是上图中所做的。尽管如上所述，最佳搜索深度通常很浅，但这并不是绝对必要的，因此即使是单线程的，下降到搜索深度的 DFS 仍然非常快。
I thoroughly tested all solvers on 14 different Sudoku puzzles (specifically, a select set of puzzles specially designed to be difficult for a backtracking solver), and the figure below shows each solver's average time taken to solve all puzzles, for various thread counts (my laptop has four hardware threads). Parallel variant 2 isn't shown because it actually achieved significantly worse performance than the sequential solver. With parallel variant 1, the # threads was automatically determined during run-time, and depended on the puzzle (specifically, the branching factor of the first level); Hence the blue line represents its average total solving time regardless of the thread count.
所有并行求解器变体都以不同方式在不同程度上结合了 DFS 和 BFS。当使用 4 个线程时，最快的并行求解器（变体 4）平均比单线程求解器快三倍！
当您说给定难题的所有解决方案时，您是指该难题的最后一个也是唯一的解决方案吗？还是达成一种解决方案的不同方式？我的理解是，根据定义，数独谜题只能有一个解决方案......
对于前者，Pax 的基于规则的方法或Tom Leys 对现有回溯算法的多线程处理可能是可行的方法。
如果是后者，您可以实现某种分支算法，该算法在拼图的每个阶段为每个可能的移动启动一个新线程（带有它自己的拼图副本）。
它是否需要从多线程中受益，或者只是利用多线程来学习作业？
如果您使用蛮力算法，则很容易拆分为多个线程，并且如果分配专注于编码线程，这可能是一个可接受的解决方案。
根据您对单线程求解器的编码方式，您可能能够重用该逻辑。您可以编写一个多线程求解器，以使用一组不同的策略启动每个线程来解决难题。
使用这些不同的策略，您的多线程求解器可能会在比单线程求解器更短的时间内找到全部解决方案（请记住，尽管真正的数独难题只有一个解决方案……但您并不是唯一一个不得不在课堂上处理那个糟糕透顶的游戏）
一些一般要点：我不会并行运行进程，除非 1) 很容易划分问题 2) 我知道这样做会有所帮助 - 例如，我不会遇到另一个瓶颈。我完全避免在线程之间共享可变值 - 或最小化它。有些人足够聪明，可以安全地使用互斥锁。我不是。
您需要在算法中找到创建自然分支或大型工作单元的点。一旦确定了要工作的单元，就将其放入队列中以供线程拾取。作为一个简单的例子。10 个数据库要升级。在所有 10 台服务器上开始异步升级。等待全部完成。我可以轻松避免线程/进程之间共享状态，并且可以轻松汇总结果。
对于数独，我想到的是一个有效的数独解决方案应该结合 2-3 个（或更多）策略，这些策略永远不会超过一定的深度。当我做数独时，很明显，在任何给定时刻，不同的算法提供的解决方案工作量最少。您可以简单地启动一些策略，让他们调查到有限的深度，等待报告。冲洗，重复。这避免了“暴力破解”解决方案。每个算法都有自己的数据空间，但你可以组合答案。
Sciam.com 在一两年前就有关于这方面的文章——不过看起来它并不公开。
您说您使用回溯来解决问题。您可以做的是将搜索空间分成两个并将每个空间处理给一个线程，然后每个线程都会执行相同的操作，直到您到达最后一个节点。我对此做了一个解决方案，可以在 www2.cs.uregina.ca/~hmer200a 找到，但是使用单线程，但是使用分支和绑定分割搜索空间的机制是存在的。
几年前，当我研究解决数独时，似乎最佳解决方案使用了逻辑分析算法的组合，并且仅在必要时才使用蛮力。这使求解器能够非常快速地找到解决方案，并且如果您想使用它来生成新的谜题，还可以按难度对棋盘进行排名。如果您采用这种方法，您当然可以引入一些并发性，尽管让线程实际一起工作可能会很棘手。
我有一个很有趣的想法……用演员模型来做！我会说使用erlang ..怎么样？你从原来的板子开始，然后..
显然，每个幸存的参与者都是问题的解决方案 =)
只是一个旁注。我实际上实现了一个优化的数独求解器并研究了多线程，但有两件事阻止了我。
首先，启动一个线程的简单开销需要 0.5 毫秒，而整个解析需要 1 到 3 毫秒（我使用的是 Java，其他语言或环境可能会给出不同的结果）。
其次，大多数问题不需要任何回溯。而那些这样做的人，只需要在解决问题的后期，一旦所有的游戏规则都用尽了，我们需要做出一个假设。
这是我自己的一分钱。希望能帮助到你。
请记住，处理器间/线程间通信是昂贵的。除非必须，否则不要使用多线程。如果在其他线程中没有太多工作/计算要完成，您还不如继续使用单线程。
尽量避免线程间共享数据。仅在必要时使用它们
尽可能利用SIMD 扩展。借助矢量扩展，您可以一次对多个数据执行计算。它可以帮助你很多。