私はスーダックチェッカー/ソルバーを簡単に作ったが、複数の解決策があり、その周りを頭で囲むことができなかった。私は動作するアルゴリズムを見つけましたが、なぜ動作するのか理解しようとしています。なお、以下にコピーされ@fabianJava：再帰的なスドクソルーションカウントアルゴリズム
によって提供さthis questionからの回答、です：
// returns 0, 1 or more than 1 depending on whether 0, 1 or more than 1 solutions are found
static byte solve(int i, int j, int[][] cells, byte count /*initailly called with 0*/) {
if (i == 9) {
i = 0;
if (++j == 9)
return 1+count;
}
if (cells[i][j] != 0) // skip filled cells
return solve(i+1,j,cells, count);
// search for 2 solutions instead of 1
// break, if 2 solutions are found
for (int val = 1; val <= 9 && count < 2; ++val) {
if (legal(i,j,val,cells)) {
cells[i][j] = val;
// add additional solutions
count = solve(i+1,j,cells, count));
}
}
cells[i][j] = 0; // reset on backtrack
return count;
}
私はそれを実装してみました、そしてそれが必要として、それが動作します。しかし、それぞれのコードのの部分が何を理解しているかとは思いますが、なぜそれが機能するのか理解できません。
最初：最初のifステートメントは、2次元配列の最後の数値に達するとメソッドを停止します。私はこれを単一の解決策を見つけるのに得ますが、なぜそれが複数の解決策を見つけるのに役立ちますか？ソリューションが見つかったらメソッドはちょうど0 + 1 = 1を返してはいけませんか？
第二：if (cells[i][j] != 0)後、なぜ再帰solve(...)呼び出しはその前にreturn文を必要とするのか？私はいくつかの再帰的なアルゴリズムを作ってきましたが、常にメソッドをもう一度呼び出すだけです。
第3の：適切な数字が見つからない場合は、ループが停止し、セルの場所に0が入力されます。それはすでに0であるはずなので、バックトラッキングではなく、最後の場所に0を入れてはいけませんか？少なくともそれは私が自分で作ったソルバーを作った方法です。
第4の：バックトラックセット後、ちょうどreturn countがあります。なぜプログラムはまだ動作していますか？ count = 0を返すべきではありませんし、何も数字を許可しない最初の場所に直面した後に停止するべきではありませんか？最後に再帰呼び出しがないのはどうですか？
これまでのところ、このような質問に答えると、いくつかのことを完全に間違って理解していることは明らかです。私は非常に支援/説明を理解していただければ幸いです。 Googleが優雅にハーバード大学からパワーポイント講義提供して