我有一个家庭作业，要编写一个多线程数独求解器，它可以找到给定谜题的所有解决方案。我之前写过一个非常快速的单线程回溯数独求解器，所以我在数独求解方面不需要任何帮助。
我的问题可能与不真正理解并发性有关，但我看不出这个问题如何从多线程中受益。我不明白如何在不维护拼图的多个副本的情况下同时找到同一问题的不同解决方案。鉴于这个假设(请证明它是错误的)，我看不出多线程解决方案如何比单线程更有效。
如果有人能给我一些关于算法的入门建议，我将不胜感激(请不要代码...)
我忘了说，要使用的线程数是作为程序的参数指定的，所以据我所知，它与拼图的状态没有任何关系...
此外，可能没有唯一的解决方案 - 有效的输入可能是一个完全空的板。我必须报告 min(1000, number of solutions) 并显示其中之一(如果存在)
最佳答案
真的很简单。基本概念是，在您的回溯解决方案中，您将在有选择时进行分支。您尝试了一个分支，回溯，然后尝试了另一种选择。
现在，为每个选项生成一个线程并同时尝试它们。如果系统中已有 < 一些线程(这将是您的输入参数)，则仅生成一个新线程，否则只需使用简单的(即您现有的)单线程解决方案。为了提高效率，请从线程池中获取这些工作线程。
这在许多方面是一种分而治之的技术，您将选择作为一个机会，将搜索空间分成两半，并将一半分配给每个线程。很可能有一半比另一半更难，这意味着线程生命周期会有所不同，但这就是优化的有趣之处。
处理明显的同步问题的简单方法是复制当前板状态并将其传递给函数的每个实例，因此它是函数参数。这种复制意味着您不必担心任何共享并发。如果您的单线程解决方案使用全局变量或成员变量来存储板状态，则您将需要在堆栈上(简单)或每个线程(更难)上的副本。您需要返回的所有函数都是一个棋盘状态以及为达到该状态而采取的一些 Action 。
每个调用多个线程来完成工作的例程应该在有 n 个工作时调用 n-1 个线程，完成第 n 个工作，然后使用同步对象等待，直到所有其他线程完成。然后你评估他们的结果 - 你有 n 个棋盘状态，返回移动次数最少的那个。
关于java - 解决数独的多线程算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/850866/