This Link verfügt über eine Backtracking-Implementierung des Sudoku Solver-Algorithmus. Beachten Sie, dass Zeile 42 den ursprünglich einer Zelle zugewiesenen Wert auf einen anderen Wert zurücksetzt, falls der ursprünglich zugewiesene Wert keine gültige Ausgabe ergab.Wie funktioniert diese Implementierung von Sudoku-Solver trotz nicht gespeicherten Zustand?
Allerdings verstehe ich nicht, wie allein die Änderung des Wertes dieser Zelle ausreicht. Dieser Aufruf könnte viele andere Aufrufe ausgelöst haben, und da Arrays (Matrizen) von Speicher (Referenz) übergeben werden, behält es keine Kopie der Matrix (Gitter [N] [N]) bei jedem Aufruf des rekursiven Funktion und ändert sich so, bis der Basisfall der Rekursion selbst im ersten Rekursionsrahmen bis zum Zeitpunkt der Rückkehr reflektiert wird.
Nach mir, kurz vor dem Aufruf der rekursiven Funktion, sollten Sie eine temporäre Kopie von Gitter [N] [N] machen und wiederherstellen, sobald der Aufruf zurückgegeben wird, und bevor die nächste Funktion im selben Rahmen ist namens.
So etwas wie
for (int num = 1; num <= N; num++)
{
// if looks promising
if (isSafe(grid, row, col, num))
{
//save grid state
int[][] temp = new int[N][N];
save(temp,grid); //copy all values from grid to temp
// make tentative assignment
grid[row][col] = num;
// return, if success, yay!
if (SolveSudoku(grid))
return true;
//restore grid state
restore(temp,grid); //copy all values from temp back to grid
// failure, unmake & try again
grid[row][col] = UNASSIGNED;
}
}
Bitte helfen Sie mir dieses Detail zu verstehen.
Es ist nicht möglich, eine verbindliche Antwort zu liefern, ohne den Rest des Codes zu untersuchen. aber stackoverflow.com ist nicht wirklich ein Ort dafür. Obwohl es scheint, dass die Rückkopie des ursprünglichen Rasters unnötig ist, da die 'UNASSIGNED'-Zuweisung die Bewegung wieder zurückzusetzen scheint, kann ich nicht wirklich mit 100% Sicherheit sagen. Genau dafür ist ein Debugger gedacht. Verwenden Sie dieses sehr nützliche Tool, das Sie auf Ihrem Computer finden, um Schritt für Schritt durch diesen Code zu gehen und zu sehen, wie es funktioniert, ganz allein, ohne dass Sie Fremde im Internet um Hilfe bitten müssen. –
Bei jeder Rekursionsstufe weist der Code eine Zelle zu und setzt eine Zelle zurück. Das Speichern des gesamten Gitters ist nicht erforderlich, da der ursprüngliche Zustand nach jedem rekursiven Aufruf eine Zelle nach der anderen wiederhergestellt wird. Man könnte sagen, dass der vollständige Zustand auf dem Aufruf-Stack in der lokalen Variablen Zeile und Spalte gespeichert ist, die auf jeder Rekursionsebene gespeichert werden. – samgak