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?
CodePudding user response：
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:
- Dequeue a grid state from the queue.
- Take the next free cell.
- Determine which values this free cell can get without violating any of the rules you listed.
- Create a grid state for each of these, and enqueue them.
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.