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

Question

我正在使用此YouTube视频中描述的回溯算法.

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

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 guesses
if you recorded a solution then the puzzle is solvable.

如果您想要所有解决方案,那么只需将算法修改为:

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 guesses
if you recorded any solution then the puzzle is solvable.

顺便说一句,我写了一系列关于使用图形着色回溯算法在C#中解决数独的博客文章; 你可能会感兴趣:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

在此代码中,您将看到以下行:

return solutions.FirstOrDefault();

"solutions"包含一个枚举所有解决方案的查询.我只想要第一个这样的解决方案,所以这就是我的要求.如果你想要每个解决方案,只需重写程序,使其不会调用FirstOrDefault.有关注释,请参阅下面的注释.