✔ Rekursion - Verständnisfrage

[Dragonate]

Moin Leute,

ich arbeite immer noch an meinem Sudoku-Programm, und will im Bezug auf Back-Tracking jetzt die Rekursion anwenden.

Dazu ist meinem Fall notwendig, das sich die Main-Funktion an einer bestimmten Stelle wieder selbst aufruft.
Funktioniert das bei der Main-Funktion ? Oder ist diese, weil sie die Hauptfunktion ist davon ausgeschlossen ?

Und wenn sich diese dann erneut aufruft, nehmen alle Werte innerhalb der Main Funktion wieder Ihren Ursprungswert an richtig ?

 

[deepthroat]

Hi.

ich arbeite immer noch an meinem Sudoku-Programm, und will im Bezug auf Back-Tracking jetzt die Rekursion anwenden.

Dazu ist meinem Fall notwendig, das sich die Main-Funktion an einer bestimmten Stelle wieder selbst aufruft.
Funktioniert das bei der Main-Funktion ?

Ja.

Und wenn sich diese dann erneut aufruft, nehmen alle Werte innerhalb der Main Funktion wieder Ihren Ursprungswert an richtig ?

Was meinst du mit "Werte"? Lokale Variablen werden natürlich neu initialisiert und auf den Stack gepusht.

Gruß

 

[Jellysheep]

Funktioniert das bei der Main-Funktion ? Oder ist diese, weil sie die Hauptfunktion ist davon ausgeschlossen ?
Und wenn sich diese dann erneut aufruft, nehmen alle Werte innerhalb der Main Funktion wieder Ihren Ursprungswert an richtig ?

Das geht, und die Werte sind wieder komplett neu.

 

[Dragonate]

Jo mit Werten meinte ich die lokalen Variablen, genau.

Gut dann ist alles klar, danke.

 

[Vereth]

Trotzdem rate ich dir, die main-Methode nicht rekursiv zu verwenden, weil sie dazu da ist, alle möglichen Vorarbeiten zu machen. Schreibe dir für die Lösungssuche am besten eine eigene solve()-Funktion, die dann rekursiv verwendet werden kann. Und achte darauf, dass globale Variablen, in deinem Fall z.B. das Spielfeld, 'von Hand' auf ihren ursprünglichen Wert zurückgesetzt werden müssen.

 

[Dragonate]

Jo hab ich dran gedacht !

Sieht schon nicht schlecht aus, ich steck mitten in der Schwierigkeit vom Backtracking.

Mein Programm löst schon leichtere Sudokus, und dem schwererem Fall nähere ich mich, wenn ich das komplett hinkrig kann ich ja vielleicht wenn es wen interessiert, meinen Code mal posten, wird aber noch etwas dauern ^^

 

[Vereth]

Möglicherweise kannst du die Laufzeit verkürzen, indem du dir immer das Feld mit den wenigsten Kandidaten bzw. die Zahl mit den wenigsten Platzierungsmöglichkeiten raussuchst. Diese Art des 'decision pruning' ist eigentlich ziemlich oft erfolgreich.

 

[Dragonate]

Das stimmt, das ist eine gute Idee @ Vereth, die ich auch noch nicht einbezogen habe. Werde ich nachträglich wenn das Backtracking, und somit das Lösen von komplizierteren Sudokus funktioniert, zur Optimierung mit einbauen.

Die Effizienz ist glaube ich bei meinem Prinzip auch schon recht gut, vorhandene und nachträglich eingesetzte Werte werden entsprechend entfernt, sodass das die Lösungsgeschwindigkeit progressiv ansteigt.

Wenn ich dann noch deine Methode miteinbinde, sollte es schon super schnell laufen