Sudoku-Lösungsalgorithmus mit Rückverfolgung

Ich möchte einen sehr einfachen Algorithmus implementieren, der Brute-Force-Back-Tracking verwendet, um Sudoku-Gitter zu lösen. Das Problem, vor dem ich stehe, ist, dass ich in meiner Implementierung zwei Instanzvariablen für a eingeschlossen habeSudoku Klasse namensrow undcol, die der Zeile und Spalte einer leeren Zelle in einem zweidimensionalen Array entsprechen, das das Sudoku-Gitter darstellt.

Wenn meinesolve() Die Methode prüft zunächst, ob keine leeren Zellen vorhanden sind. In diesem Fall ist das Rätsel bereits abgeschlossen. Andernfalls weist dieselbe Methode den Instanzvariablen die Zeile und Spalte einer leeren Zelle zurow undcol desSudoku Objekt, das das Raster enthält. Anschließend überprüft die for-Schleife, welche Nummer durch einen Methodenaufruf in diese leere Zelle eingefügt werden kannisSafe(int n) (Diese Methode prüft, ob die Bedingungen des Puzzles erfüllt sind. Ich kann garantieren, dass es einwandfrei funktioniert.) Also, dieisSafe() Methode platziert eine Zahl in der leeren Zelle und ruft dann rekursiv die aufsolve() Methode erneut auf dieSudoku Objekt.

Wenn wir eine Einschränkung treffen, die nicht erfüllt werden kann, weisen wir a neu zu0 bis zum letztenrow undcol das war gefüllt. Hier liegt das Problem! Da das Programm ständig aktualisiertrow undcol Variablen dann gehen die alten Instanzen bei jedem rekursiven Aufruf verloren. Ich habe versucht, herauszufinden, wie diese Werte gespeichert werden, damit das Programm Aktionen rückgängig machen kann, wenn es zurückverfolgt. Ich habe darüber nachgedacht, jeden zu schiebencol undrow zu einem Stapel, aber ich bin wirklich nicht sicher, wohin ich gehen soll.

Kann mir jemand sagen, was ein einfacher Weg wäre, um dieses Problem anzugehen? Ich beziehe nicht die gesamte Klasse mit ein, wenn du denkst, dass es hilfreich ist, lass es mich wissen und ich werde es posten.

class Sudoku {
    int SIZE, N, row, col;
    int Grid[][];    

    public boolean solve() {
        if (!this.findNextZero()) return true;

        for (int num = 1; num <= 9; num++) {
            if (isSafe(num)) {
                this.Grid[this.row][this.col] = num;

                if (this.solve()) return true;

                this.Grid[this.row][this.col] = 0;
                // this.Grid[oldRow][oldCol] = 0;
            }
        }
        return false;
    }

    public boolean findNextZero() {
        for (int i = 0; i < this.N; i++) {
            for (int j = 0; j < this.N; j++) {
                if (this.Grid[i][j] == 0) {
                    this.row = i;
                    this.col = j;
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isSafe(int num) {
        return !this.usedInRow(num) 
                && !this.usedInColumn(num) 
                && !this.usedInBox(num);
    }

Wenn ich einen Stack implementieren würde, ist Folgendes sinnvoll? Nach demfindNextZero() Operationen schieben dierow undcol ganze Zahlen auf den Stapel. Machen Sie so weiter und ändern Sie dann die folgende Codezeile

this.Grid[this.row][this.col] = 0;

zu so etwas wie

this.Grid[s.pop][s.pop] = 0;

Ist das ein vernünftiger Ansatz?