我有一个家庭作业来编写一个多线程数独求解器，它可以找到给定难题的所有解决方案。我以前写过一个非常快速的单线程回溯数独求解器，所以我不需要任何关于数独求解方面的帮助。
我的问题可能与没有真正摸索并发有关，但我不明白这个问题如何从多线程中受益。我不明白如何在不维护拼图的多个副本的情况下同时找到同一问题的不同解决方案。鉴于这个假设（请证明它是错误的），我不认为多线程解决方案比单线程解决方案更有效。
如果有人能给我一些关于算法的起始建议，我将不胜感激（请不要编写代码...）
我忘了提一下，要使用的线程数被指定为程序的参数，因此据我所知，它与谜题的状态没有任何关系......
此外，可能没有唯一的解决方案 - 有效的输入可能是一个完全空的电路板。我必须报告并显示其中一个（如果存在）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，解决方案数量）并显示其中一个（如果存在）
看起来你的老师不希望你根据规则进行拆分，而是根据分叉点（可以应用多个规则）进行拆分。
我的意思是，在解决方案的任何时候，如果有两个或更多可能的前进，你应该将每个可能性分配给一个单独的线程（仍然使用你的规则来提高效率，但同时检查每种可能性）。这将为您提供更好的并发性（假设线程可以在单独的CPU/内核上运行），因为不会有对电路板的争用;每个线程都将获得自己的副本。
此外，由于您要限制线程的数量，因此您必须使用一些线程池魔术来实现此目的。
我的建议是有一个工作队列和N个线程。当主线程启动所有工作线程时，工作队列最初为空。然后，主线程将开始的拼图状态放入工作队列中。
工作线程只需等待将状态放置在工作队列上，其中一个线程会抓取该状态进行处理。工作线程是您的单线程求解器，只需进行一次小的修改：当有 X 种可能性向前推进（X > 1）时，您的工作线程会将其中 X-1 放回工作队列，然后继续处理另一种可能性。
所以，假设只有一个解决方案（真正的数独：-）。第一个工作线程将在找不到任何分支的情况下减少解决方案，这将与您当前的情况完全相同。
但是，在移动 27 处有两种可能性（例如，3 或 4 可以进入左上角的单元格），您的线程将创建另一个具有第一种可能性的板（将 3 放入该单元格中）并将其放置在工作队列中。然后它会把4放在自己的副本中并继续。
另一个线程将拾取该单元中带有3的板并继续进行。这样，您就有两个线程同时运行，处理这两种可能性。
当任何线程确定其电路板不溶时，它会将其丢弃并返回到工作队列以进行更多工作。
当任何线程决定其电路板已解决时，它会通知可以存储它的主线程，覆盖任何以前的解决方案（首先找到的是解决方案）或将其丢弃（最后找到的是解决方案），然后工作线程返回到工作队列进行更多工作。在任一情况下，主线程都应增加找到的解决方案计数。
当所有线程都空闲并且工作队列为空时，main 将有或没有解决方案。它还将有一系列解决方案。
请记住，worker 和 main thread 之间的所有通信都需要互斥（我假设您根据问题中的信息知道这一点）。
