c# - バックトラッキングアルゴリズムを使用してすべての可能なソリューションを取得する方法は?

Question

この YouTube ビデオ で説明されているバックトラッキング アルゴリズムを使用しています。

これで、すべての可能なソリューションを取得できるはずです。バックトラッキングアルゴリズムでこれを行うことはできますか? 不可能な場合、他のどの (単純な) アルゴリズムを使用する必要がありますか?

Answer 1

この質問は、実際のコードに関するものではないように見えるため、このサイトにはあまり適していません。

でも、とにかく狙ってみます。

もちろん、バックトラッキング アルゴリズムを使用して、考えられるすべてのソリューションを取得できます。バックトラッキング アルゴリズムがどのように機能するかを思い出してください。

while(利用可能な推測がまだあります)
    推測する
    推測でパズルを解く
    解決策があった場合は、解決策を記録してループを終了します。
    可能な推測のリストから推測を消す
解決策を記録した場合、パズルは解決可能です。

すべてのソリューションが必要な場合は、アルゴリズムを次のように変更します。

while(利用可能な推測がまだあります)
    推測する
    推測でパズルを解く
    解決策があった場合は、解決策を記録します。やめないで。
    可能な推測のリストから推測を消す
解決策を記録した場合、パズルは解決可能です。

ちなみに、私はグラフ色付けバックトラッキング アルゴリズムを使用して C# で数独を解く方法に関する一連のブログ記事を書きました。それはあなたにとって興味深いかもしれません：

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

このコードでは、次の行が表示されます。

return solutions.FirstOrDefault();

"solutions" には、すべてのソリューションを列挙するクエリが含まれています。私は最初のそのような解決策だけが欲しいので、それを求めています。すべての解決策が必要な場合は、 を呼び出さないようにプログラムを書き直してくださいFirstOrDefault。いくつかのメモについては、以下のコメントを参照してください。