2
我很輕鬆地製作了Sudoku檢查器/求解器，但是我需要一個能夠告訴我有多個解決方案的解決方案，並且無法將其包裹在它周圍。我發現了一個工作算法，但我試圖理解它爲什麼工作。這是從this question，答案由@fabianJava：遞歸數獨解法計數算法
複製以下提供：
// 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聲明？我做了幾個遞歸算法，但總是通過再次調用該方法。
第三：如果沒有找到合適的數字，則for循環停止，並且0被輸入到單元格位置。由於它應該已經有0，不應該回溯到0而不是當前的最後一個地方？至少我是這樣解決自己的問題的。
第四：在回溯設置後，只有return count。爲什麼程序還在工作？不應該只是返回count = 0，並在面對不允許任何數字的第一個地方後停止？如何在最後沒有遞歸調用？
如果你在這個棘手的問題上做得這麼遠，很顯然，我理解一些完全錯誤的東西。我非常感謝幫助/解釋，因爲使用代碼不理解的代碼是完全失敗的。