Endergebnis einer rekursiven Methode

[timbeau]

Hallo und guten Abend zusammen.

Ich lese hier regelmäßig aber habe in der SuFu leider keine passende Antwort gefunden.

Mein Problem ist das Folgende:
Ich habe aus Spaß ein Programm geschrieben, welches mir ein Sudoku füllt. Dieses lese ich über eine Swing-Gui ein. Um die Ausgabe ebenfalls in dieser Gui anzuzeigen habe ich mir gedacht, dass ich ja die 81 JTextfields neu befülle. Dabei stellt sich mir die Frage die ich bisher nicht lösen konnte (wahrscheinlich Brett vorm Kopf), wie bekomme ich das letzte Ergebnis der folgenden Methode:

Aufruf (Sudoku)
Prüfen ob das Sudoku gelöst ist und dann dieses Feld zurückgeben
Wenn nicht eine Zahl einfügen und mit dem neuen Feld aufrufen und return Null

Wie kann ich in meiner Gui nun auf die Lösung des Sudokus warten. Wenn ich schreibe

while(true) {
if(Lösung = rekursiveMethode(Sudoku)!= null) {
Zeichne GUI
}

generiert er mir natürlich endlos viele Methoden. Direkt Lösung = rekursiveMethode gibt mir ja ein Null zurück.

Vermutlich ist es ganz einfach. Sollte ich Informationen vergessen/unterschlagen haben, nicht schimpfen, ich liefere sie nach ;-)

Danke schonmal

 

[Cola_Colin]

Die Methode zum Lösen in einen Thread verpacken und darauf warten, das der Fertig wird ?
Deine Lösungsmethode wird doch wohl nicht direkt mit dem UI als Datenquelle arbeiten ?

 

[XHelp]

Wo hast du denn diesen Lösungsansatz her? Es sieht verdächtig dannach aus, als ob du den ganzen Baum aufbaust, dann sollte es ähnlich aussehen wie:

boolean sudokuLoesbar(Spielfeld) {
  Keine Züge möglich?
    Ist die Lösung korrekt?
      gib true zurück

  für alle Möglichen Züge:
    neuesSpielfeld = machDenZug()
    wenn (sudokuLoesbar(neuesSpielfeld))
      dann gib true zurück

  gib false zurück
}

Aber ich bin mir sicher, dass es effizientere Lösungsansätze gibt.

 

[timbeau]

Das Programm hab ich eigentlich angefangen um mich in die Swing-Programmierung einzuarbeiten. Ist dann allerdings doch mehr in den reinen 'Java'-Bereich abgerutscht.

Das komplette Programm baut ein Sudoku aus den einzelnen Feldern(eigene Klasse) die jeweils für sich ihre möglichen Zahlen prüfen und hält sie in einem Array vor.

Meine rekursive-Methode setzt halt die Zahlen aus dem kürzesten Array ein, prüft, berechnet die Felder neu, setzt wieder die Zahl aus dem kürzesten Array ein und geht rekursiv zurück wenn sie irgendwo hängt bzw wenn es keine Lösung gibt, sagt sie das auch.

Und das ganze funktioniert auch. Auf der Konsole bekomme ich das gelöste Sudoku zurück wenn ich es per Gui eingebe und die rekursive Methode starte. Ich gehe allerdings alle Äste des Baums lang bis ich an eine Sackgasse komme. Aber bei 81 Feldern ist das mE vernachlässigbar.

Bzgl Threads habe ich mir auch schon gedacht. Aber der Thread muss ja auch irgendwie merken, dass die rekursive Methode zu Ende gerechnet hat aber eben nur dann wenn eine Lösung gefunden wurde und sich dann auf jeden Fall beenden. Meine Methode gibt nämlich alle(?) möglichen Lösungen zurück, wenn ich also nur 1 Zahl eingebe spuckt er mir dutzende unterschiedliche Sudokus aus. Das ist zwar nett aber muss ja nicht sein. Jetzt muss also der Thread beendet werden und das gelöste Sudoku zurückgeben. Zusätzlich muss der main-thread ja warten. Und in welche Klasse muss der Thread am besten? In die der GUI oder in die Klasse des Sudokufeldes welches alle weiteren Operationen steuert.

Wäre schön, wenn ihr mir hier weiterhelfen könntet.

 

[Marcinek]

Hallo,

sobald der Thread zu ende ist löst er ein Ereignis aus: (Action)

Der dazugehörige ActionListener macht dann irgentwas damit. Alternativ ändert der Thread dann entspechend die UI ab um ddas Ergebnis darzustellen.

Ein Thread wird dann einfach beendet, wenn sein Code komplett ausgeführt worden ist.

Blockierende aufrufe halten alles an und es wird gerechnet, bis es fertig ist.

Möchtest du jeden rekursiven aufruf in einem Thread starten? - So funktionieren Rekursionen nicht.

Jeder Aufruf einer Rekursion blockiert und es wird intern duzende verweise (Rücksprungspunkte) generiert, die bei dem letzten aufruf der Rekursion zurückgesprungen werden.

Gruß,

Martin

 

[timbeau]

Nein, ein Thread für die rekursive Methode. Wie kann ich aber den Thread also nun wenn er fertig ist dazu veranlassen eine Gui zu ändern mit dem Ergebnis des "letzten" Aufrufs der rekursiven Methode?

Wäre eine Möglichkeit eine Variable außerhalb des Threads zu überschreiben bei gelöstem Sudoku und nach Beendigung des Threads einfach diese auslesen?

Muss ich morgen mal testen.

 

[Marcinek]

Entweder du gibst dem Thread eine referenz auf deine GUI und er stellt dir das Ergebis dann dar.

Oder eine Referenz auf das Model und bei aktualisierung des Models => Aktualisierung der GUI.

trivial.

 

[timbeau]

Vielleicht drücke ich mich undeutlich aus oder es ist für euch zu einfach . Ich habe eine unvorhersehbare Menge an Rückgabewerten. Irgendwo in diesem Baum findet meine Methode nun eine Lösung. Diese möchte ich sofort zurückgeben und die Methode inkl. aller weiteren rekursiven Aufrufe beenden. Kann ich sowas aufrufen:

Thread startet Methode einer Klasse und die Methode bricht mit System.exit(X) ab?

 

[XHelp]

So läuft Rekursion nicht ab. Du könntest natürlich es etwas abändern, z.B.

rek() {
  bei Abbruchbedingung: rufe rekZuEnde(ergebnis) auf
  ansonsten rek();

Wenn du fertig bist, dann wird eben eine Methode aufgerufen, der Rückgabewert wird dabei ignoriert.

 

[timbeau]

Hey danke. Das klingt gut.

Aber bzgl "so läuft Rekursion nicht". Wenn ich einen Baum durchgehe mach ich doch auch nichts anderes. Ob ich die Ergebnisse nun sammle oder wie beim "Rucksackproblem" bzw Backtracking irgendwo halt mache ist doch im Prinzip egal. Bitte um Erläuterung

 

[XHelp]

Naja, beim Backtraing wird ja auch ein Wert zurückgegeben.
Du kannst ja eine rekursive Methode schreiben, der du ein unvollständiges Sudoku übergibst und sie dir ein vollständiges zurückliefert, falls möglich.
Dann musst du auch nicht den Code bis zum Unmöglichen ineinander verstricken.

 

[timbeau]

Genau das tu ich hier. Die Funktion ruft sich immer mit dem "neuen" Sudoku auf. Und wenn das Sudoku gelöst ist, möchte ich eine Meldung bekommen bzw das Sudoku zurück. Solange keine Lösung gefunden wurde bzw ganz am Ende gebe ich NULL zurück.

Okay, meine Lösung ist vielleicht nicht perfekt aber reicht. SObald eine Lösung gefunden wurde, wird diese in eine Klassenvariable geschrieben. Am Anfang der backtrack-Methode wird diese überprüft und bei NotNull wird returned. Damit laufen alle noch offenen Äste ins nichts und die Methode hört schnell auf.