Sudoku Solver funktioniert beim 2. Aufruf nicht mehr

[steve]

Hallo,

ich programmiere gerade Sudoku mit integriertem Solver.

Das lösen funktioniert auch prima, bis ich ihn das zweite mal aufrufe. Dann hält er kurz vor der 6. Zeile an; mit einem StackOverflowError.

Hier der solver:

public void solve(Integer r, Integer c) {
//wenn das Sudoku noch nicht gelöst ist
		if (isValid(data) == false) {
			if (c > n - 1) { //Spalten- und Zeilenangaben überprüfen und korrigieren
				r++;
				c = 0;
			}
			if (c < 0) {
				r--;
				c = 8;
			}

			if (sudokuData[r][c] == 0) {//Falls das aktuelle Feld verändert werden darf
				data[r][c]++;//Feld setzen
				if (data[r][c] <= n) {//Falls die gesetzte Zahl nicht größer als 9 ist
					if (isNumberValid(data, r, c)) {//falls der gesetzte Inhalt gültig ist
						back = false;
						solve(r, c + 1);//nächstes Feld aufrufen
					} else {
						back = false;
						solve(r, c);
					}
				} else {
					back = true;//Schritt rückgängig machen
					data[r][c] = 0;
					solve(r, c - 1);
				}
			} else {//wenn das Feld nicht verändert werden darf: nächstes/vorheriges Feld aufrufen
				if (back == false) {
					back = false;
					solve(r, c + 1);
				} else {
					back = true;
					solve(r, c - 1);
				}
			}
		}
	}

Und so wird er aufgerufen von einer anderen Klasse aufgerufen:

	public void solveSudoku() {
		solver.setData(sudokuData.getSudokuData());//übergibt das Sudokuarray an die Solver Klasse
		solver.solveSudoku(0,0);//ruft den solver auf
		data = solver.getData();//holt sich die daten des gelösten Sudokus
		tableModel.setHoleValueAt((Object[][]) data);//übergibt dem TableModel die Daten
	}

Ich hatte zuvor noch einen Parameter: private void solve(Integer r, Integer c, Integer z).
In dem Fall hat er noch nicht mal einen Durcchgang geschafft.

Ich hoffe ihr könnt mir helfen. Ich sitze nämlich schon ein paar Tage daran.

Gruß
Steve

 

[dieta]

Der Fehler kommt daher, dass die Methode sich rekursiv immer und immer wieder selbst aufrüft, und irgendwann einfach der Aufrufasspeicher (Stack) voll ist.

 

[steve]

Mh, aber der Algorithmus funktioniert beim 1. Mal sehr gut und löst ein bestimmtes Sudoku erfolgreich. Wenn ich ihn aber mit genau dem selben Sudoku nochmal aufrufe geht er bis zur 6. Zeile und dann ist Schluss.

 

[dieta]

Ja, denn da ist dann der Stack voll und das Programm stürzt ab.

 

[steve]

Kann ich den Stack irgendwie vor dem 2. Aufruf leeren oder muss ich einen optimierten Algorithmus schreiben?

 

[dieta]

DU kannst den Stack leeren, indem du die Methoden, in die du gehst wieder verlässt. Der überfüllte Stack sieht dann so aus:

bla
  bla
    bla
      bla
        bla
          ...
            bla

und da ist dann halt irgendwann der Speicher voll mit bla.
Du musst die Methode, nach ihrem Betreten auch irgendwann wieder verlassen, damit sie aus dem Stack gelöscht werden kann (Das ist dei warscheinlichste Fehlerursache, dass du das nämlich nicht tust).

 

[steve]

Mh, ich dachte immer Methoden werden automatisch verlassen. Ich komme nämlich von der Delphi-Ecke und habe einfach übertragen. Muss ich dann am Ende der Methode immer return aufrufen, oder wie verlasse ich die Methode sonst?

 

[Apo]

wenn du eine void Methode hast, wo du nichts zurückgibst, brauchst du eigentlich kein return;
das return verlässt die Methode dann nur sofort an der Stelle und Java ist es egal was danach in der Methode noch stehen würde ...

oder du zwingst Java mit

System.gc();

den Speicher zu entleeren von Sachen, die nicht mehr gebraucht werden.

vielleicht hast du auch bei den anderen Methoden die du geschrieben hast etwas überflüssiges mit drin, was den Speicher vollhaut. Ich habe mal einen Solver geschrieben mithilfe vom simplen backtracking und da hatte ich 0 Speicherprobleme.

 

[steve]

Vielen Dank für die schnellen Antworten.

Ich habe es mit System.gc(); und return; versucht, aber es hat irgendwie nichts gebracht.

Deshalb habe ich einen neuen Solver geschrieben, der mir bis zu 9 rekursionsschritte pro feld spart und es funktioniert wunderbar.

Das Problem ist also umgangen, ich finde es aber trozdem komisch, dass der Aufruf von System.gc(); nach der solve() Methode nichts bringt. Naja, egal.

Vielen Dank nochmal für die Hilfe

 

[dieta]

System.gc() sagt Java nur, dass es überflüssige, nicht mehr benötigte Objektreferenzen im Heap löschen soll. Der Stack bleibt davon unberührt, da die in ihm gespeicherten Daten ja auch noch gebraucht werden, damit das Programm wieder von der rekursiven Methode bla in die Methode blubb, die bla aufgerufen hat "zurückfindet".

 

[steve]

Ok, das erklärt warum System.gc() nicht funktioniert. Aber die Methode wird ja verlassen, da das Programm weiter läuft. Also müssten die lokalen Variablen eigentlich gelöscht werden, oder?

 

[Apo]

ich meinte das System.gc() erst nach dem ersten kompletten Durchlauf ...
aber egal
hauptsache es fkt jetzt