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?