-2

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.

+3

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. –

+2

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

Antwort

3

Es ist Speichern-Status: Jeder rekursive Aufruf speichert den Status auf dem Aufruf-Stack.

Die nicht zugewiesenen Teile des Rasters werden geändert, bis eine gültige Lösung gefunden wird. Sobald dies der Fall ist, werden alle gestapelten Funktionsaufrufe beendet (Zeilen 38 und 39), wobei grid[][] in seinem gelösten Zustand verbleibt. Wenn nicht, wird die aktuelle Zelle auf ihren UNASSIGNED Wert zurückgesetzt und der nächstmögliche Wert wird versucht.

Dies ist ein Brute-Force-Löser. Vielleicht möchtest du das auch googeln.

Hoffe, das hilft.