使用迭代广度优先搜索解决数独问题
Solve Sudoku using iterative Breadth First Search
我有一个任务是使用迭代广度优先搜索算法来解决数独问题，但我正在努力将这个算法准确地应用于这个问题。
我发现我需要一个队列，我必须遍历这个队列直到它不为空。
我有以下算法来验证一个值在某个时刻是否适合特定的单元格：
- 检查一行中是否不存在这样的值。
- 检查列中是否不存在此类值。
- 检查块中是否不存在这样的值。
但是当我在某个时候继续使用这种算法时，我不得不回溯并更改之前选择的值，因为它可能会被证明是错误的。
如何使用 BFS 将回溯应用于这个数独问题？
BFS 不需要回溯。相反，BFS 为您提供了许多并行的路径。如果一条路径最终导致网格不一致，它就会死掉。唯一要做的就是什么也不做，即不要像通常那样将从它派生的下一个状态推送到队列中。
BFS 遍历本身可以通过多种方式组织，但它可能看起来像这样：
最初队列以原始网格状态开始。然后重复以下步骤，只要队列不为空且仍有空闲单元格：
- 从队列中取出一个网格状态。
- 占用下一个空闲单元格。
- 在不违反您列出的任何规则的情况下确定此空闲单元格可以获得哪些值。
- 为其中的每一个创建一个网格状态，并将它们排入队列。
当第三个项目符号步骤产生没有 可能的值时，分支将“死亡”。在那种情况下，下一步将不会排队任何东西，这正是您想要发生的。错误的道路被消除了。循环仍将继续并考虑队列中可能存在的其他替代网格。
我有一个任务是使用迭代广度优先搜索算法来解决数独问题，但我正在努力将这个算法准确地应用于这个问题。
我发现我需要一个队列，我必须遍历这个队列直到它不为空。
我有以下算法来验证一个值在某个时刻是否适合特定的单元格：
- 检查一行中是否不存在这样的值。
- 检查列中是否不存在此类值。
- 检查块中是否不存在这样的值。
但是当我在某个时候继续使用这种算法时，我不得不回溯并更改之前选择的值，因为它可能会被证明是错误的。
如何使用 BFS 将回溯应用于这个数独问题？
BFS 不需要回溯。相反，BFS 为您提供了许多并行的路径。如果一条路径最终导致网格不一致，它就会死掉。唯一要做的就是什么也不做，即不要像通常那样将从它派生的下一个状态推送到队列中。
BFS 遍历本身可以通过多种方式组织，但它可能看起来像这样：
最初队列以原始网格状态开始。然后重复以下步骤，只要队列不为空且仍有空闲单元格：
- 从队列中取出一个网格状态。
- 占用下一个空闲单元格。
- 在不违反您列出的任何规则的情况下确定此空闲单元格可以获得哪些值。
- 为其中的每一个创建一个网格状态，并将它们排入队列。
当第三个项目符号步骤产生没有 可能的值时，分支将“死亡”。在那种情况下，下一步将不会排队任何东西，这正是您想要发生的。错误的道路被消除了。循环仍将继续并考虑队列中可能存在的其他替代网格。