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

Question

我正在使用这个 youtube 视频中描述的回溯算法。

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

score 10 · Accepted Answer

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

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

当然，您可以使用回溯算法获得所有可能的解决方案。记住回溯算法的工作原理：

而（仍有猜测可用）
    做一个猜想
    用猜测解决难题
    如果有解决方案，则记录解决方案并退出循环。
    从可能的猜测列表中划掉猜测
如果你记录了一个解决方案，那么这个难题是可以解决的。

如果您想要所有解决方案，则只需将算法修改为：

而（仍有猜测可用）
    做一个猜想
    用猜测解决难题
    如果有解决方案，则记录解决方案。不要放弃。
    从可能的猜测列表中划掉猜测
如果您记录了任何解决方案，那么这个难题是可以解决的。

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

在此代码中，您将看到以下行：

return solutions.FirstOrDefault();

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

1 回答 1