将回溯划分为并行进程

Question

我正在尝试使用 c 中的回溯过程来解决数独 25*25 问题。有没有办法将回溯分成多个并行进程，以便我可以将它们用作线程？

Answer 1

回溯意味着深度优先搜索。

DFS 将采用以下形式：

1. 创建状态堆栈。
2. 将初始状态压入堆栈。
3. 虽然堆栈不为空，
   1. 从堆栈中弹出一个状态。
   2. 如果国家满足搜索要求，
      1. 返回状态。
   3. 对于每个可能的派生状态，
      1. 将派生状态压入堆栈。
4. 返回失败。

（递归通常用于提供堆栈，但这不是必需的。）

在数独求解器的上下文中，

1. 创建状态堆栈。
2. 将初始状态压入堆栈。
3. 虽然堆栈不为空，
   1. 从堆栈中弹出一个状态。
   2. 如果国家满足搜索要求，
      1. 返回状态。
   3. 找到一个空的方块。
   4. 对于正方形中的每个可能值，
      1. 克隆当前状态。
      2. 设置处于克隆状态的方块的值。
      3. 将克隆的状态压入堆栈。
4. 无效数独

不过，我会使用广度优先搜索。它与上面的相同，只是使用队列而不是堆栈。

我们可以轻松地将其转换为基于工人的模型。只需使用线程安全队列和一堆执行循环的线程即可。