c# - 如何使用回溯算法获得所有可能的解决方案？

Question

我正在使用描述的回溯算法 in this youtube video .

现在，我应该能够得到所有可能的解决方案。我能用回溯算法做到这一点吗？如何做？如果不可能，我应该使用哪种其他(简单)算法？

Answer 1

这个问题不太适合这个网站，因为它似乎与实际代码无关。

但无论如何我都会试一试。

当然你可以用回溯算法得到所有可能的解。记住回溯算法是如何工作的:

while(there are still guesses available)    make a guess    solve the puzzle with the guess    if there was a solution then record the solution and quit the loop.    cross the guess off the list of possible guessesif you recorded a solution then the puzzle is solvable.

If you want all solutions then just modify the algorithm to:

while(there are still guesses available)    make a guess    solve the puzzle with the guess    if there was a solution then record the solution. Don't quit.    cross the guess off the list of possible guessesif you recorded any solution then the puzzle is solvable.

Incidentally, I wrote a series of blog articles on solving sudoku in C# using a graph-colouring backtracking algorithm; it might be of interest to you:

https://learn.microsoft.com/en-us/archive/blogs/ericlippert/graph-colouring-with-simple-backtracking-part-one

In this code you'll see the line:

return solutions.FirstOrDefault();

“解决方案”包含一个枚举所有解决方案的查询。我只想要第一个这样的解决方案，所以这就是我所要求的。如果您想要所有解决方案，只需重写程序，使其不调用 FirstOrDefault。请参阅下面的评论以了解一些注意事项。