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

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 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(); 

「解決方案」包含枚舉所有的解決方案的查詢。我只想要第一個這樣的解決方案，所以這就是我所要求的。如果您想要每個解決方案，只需重寫該程序，以便它不會調用FirstOrDefault。有關注釋，請參閱下面的註釋。