Algorytm rozwiązywania sudoku ze śledzeniem wstecznym

Szukam implementacji bardzo prostego algorytmu, który używa śledzenia wstecznego sił w celu rozwiązania siatek Sudoku. Problem, przed którym stoję, polega na tym, że w mojej implementacji uwzględniłem dwie zmienne instancji dla aSudoku klasa o nazwierow icol, które odpowiadają wierszowi i kolumnie pustej komórki w dwuwymiarowej tablicy reprezentującej siatkę Sudoku.

Kiedy mojasolve() metoda wykonuje to najpierw sprawdza, czy nie ma żadnych pustych komórek, w którym to przypadku układanka jest już ukończona. W przeciwnym razie ta sama metoda przypisuje wiersz i kolumnę pustej komórki do zmiennych instancjirow icol zSudoku obiekt zawierający siatkę. Następnie pętla for sprawdza, który numer można umieścić w tej pustej komórce za pomocą wywołania metodyisSafe(int n) (Ta metoda sprawdza, czy ograniczenia układanki są spełnione, mogę zagwarantować, że działa idealnie). Tak więcisSafe() Metoda umieszcza liczbę w pustej komórce, a następnie wywołuje cykliczniesolve() metoda ponownie naSudoku obiekt.

Jeśli trafimy na ograniczenie, którego nie można spełnić, przypisujemy a0 do ostatniegorow icol to było wypełnione. W tym miejscu znaleziono problem! Ponieważ program stale aktualizujerow icol zmienne wtedy stare instancje są tracone przy każdym wywołaniu rekurencyjnym. Próbowałem dowiedzieć się, jak przechowywać te wartości, aby program mógł cofnąć działania, gdy śledzi je wstecz. Myślałem o każdym popchnięciucol irow do stosu, ale naprawdę nie jestem pewien, gdzie iść.

Czy ktoś może mi powiedzieć, jaki byłby prosty sposób na rozwiązanie tego problemu? Nie uwzględniam całej klasy, jeśli uważasz, że byłoby to pomocne, daj mi znać, a opublikuję.

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);
    }

Gdybym miał zaimplementować stos, czy poniższe ma sens? PofindNextZero() operacje naciskająrow icol liczby całkowite na stosie. Kontynuuj to, a następnie zmodyfikuj następujący wiersz kodu

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

do czegoś podobnego

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

Czy to rozsądne podejście?

questionAnswers(3)

yourAnswerToTheQuestion