使用迭代广度优先搜索求解数独
我有一项任务是使用迭代广度优先搜索算法来解决数独，但我正在努力将该算法准确地应用于这个问题。
我发现我需要一个队列，并且必须循环该队列直到它不为空。
我有以下算法来验证一个值是否在某个时刻适合特定单元格：
- 检查连续中不存在这样的值。
- 检查列中是否不存在此类值。
- 检查块中是否不存在此类值。
但是，当我在某个时候继续使用这种算法时，我必须回溯并更改之前选择的值，因为它可能是错误的。
如何使用 BFS 将回溯应用于此数独问题？
I have a task to solve sudoku using iterative Breadth first Search algorithm but I'm struggling with applying this algorithm exactly to this problem.
I figured out that I need a queue and I have to loop over this queue until it is not empty.
I have the following algorithm to validate a value whether it fits a particular cell at some moment:
- Check that no such values exist in a row.
- Check that no such values exist in a column.
- Check that no such values exist in a block.
But when I go on with such algorithm at some point I have to backtrack and change a previously selected value because it can turn out to be the wrong one.
How can I apply backtracking using BFS to this sudoku problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
BFS 中不需要回溯。相反，BFS 为您提供了许多并行路径。如果一条路径最终导致不一致的网格，它就会消亡。唯一要做的就是对它不执行任何操作，即不要像通常那样将从它派生的下一个状态推送到队列上。
BFS 遍历本身可以通过多种方式进行组织，但它可能如下所示：
最初，队列从原始网格状态开始。然后，只要队列不为空并且仍然有空闲单元，就重复以下步骤：
当第三个项目符号步骤产生没有可能的值时，分支将“死亡”。在这种情况下，下一步不会将任何内容放入队列，这正是您想要发生的情况。错误的道路就被消除了。该循环仍将继续并考虑队列中可能存在的其他替代网格。
There is no backtracking needed in BFS. Instead, BFS provides you with many paths in parallel. If one path turns out to lead to an inconsistent grid, it just dies. The only thing to do, is do nothing with it, i.e., don't push a next state derived from it on the queue, like you would normally do.
The BFS traversal itself can be organised in several ways, but here is what it could look like:
Initially the queue starts with the original grid state. Then repeat the following steps for as long as the queue is not empty and there are still free cells:
A branch will "die" when the third bullet step produces no possible values. In that case the next step will not enqueue anything, which is just what you want to happen. The wrong path is eliminated. The loop will still continue and consider other, alternative grids which may be present on the queue.