 Rekusion abbrechen |
In-Form-a-Tigger
unregistriert
 |
|
Meine Frage:
Hallo Informatiker,
ich habe folgendes Problem bei einer Aufgabe:
Ich soll die Lösbarkeit eines Sudokus überprüfen, und zwar mittels Rekursion.
Ich habe nur folgendes Problem: Mein Code prüft Stelle für Stelle, welche Zahlen möglich sind, natürlich nur, wenn das Feld leer ist. Anschließend setzt er eine der Zahlen ein, und macht an der nächsten Stelle weiter, bis er entweder das Sudoku ausgefüllt hat, oder nicht mehr weiterkommt. Ist dies der Fall, springt er zurück, und setzt einfach die nächste mögliche Zahl ein. Dieser Algorithmus funktioniert bei mir auch gut. ich erhalte am Ende ein sauber ausgefülltes Sudoku.
ABER: Er hat ja mit hoher Wahrscheinlichkeit vorher mal eine Zahl in ein Feld eingesetzt, für das zum Beispiel noch 2 weitere Zahlen möglich waren. Er springt also wieder zurück, und rechnet mit den noch nicht verwendeten Zahlen weiter. Das will ich aber nicht!
Kann ich irgendwie verhindern, dass er dann wieder in die vorherigen Teile springt?
Meine Ideen:
Ich habe ihm gesagt, er soll prüfen, ob das Sudoku vollständig ausgefüllt ist. Ich muss dann ( in der aufgabenstellung vorgeschrieben) einen boolean wert True zurückgeben, da es offensichtlich lösbar ist.
Er prüft die Lösbarkeit aber auch weiter, wenn er wieder zurückläuft, und gibt dann wieder False-Werte aus, weil er ja Zahlen einsetzt, die wahrscheinlich gar nicht mehr zu einer weiteren Lösung führen.
Ich möchte meinen Quellcode hier nicht posten und habe meine Frage deshalb allgemein gehalten, da es sich um eine Hausaufgabe handelt und diese von Mitstudenten kopiert werden könnte. Dafür bekäme ich dann ein Plagiat :-(
|
|
20.11.2011 22:52 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Besser ist es sowieso, wenn Du uns abstrakt beschreibst wie Dein Algorithmus vorgeht.
Was für Funktionen benutzt Du und wie rufst Du sie rekursiv auf?
Anhand Deiner Beschreibung kann ich Dein Problem noch nicht erkennen.
Gruß,
ED
|
|
|
20.11.2011 23:45 |
|
|
In-Form-a-Tigger
unregistriert
|
|
Um ein Beispiel zu liefern:
funktion(sudoku,x,y):
berechneMoeglicheZahlen(sudoku,x,y)
//ich ermittle zuerst die möglichen einträge für feld (x,y)
wenn(mögliche einträge vorhanden){
For-Schleife(von eintrag 0 bis zum letzten möglichen){
setze moeglicherEintrag[i] in sudoku bei (x,y) ein;
y++; // um nächstes feld zu bearbeiten
rufe funktion auf mit (sudoku,x,y); //rekursion
y--; //falls er mich zurückwirft, muss ich das y ja auch erst wieder um eins verringern
}
gibt es keine moeglichen Einträge, dann fahre fort ohne einsetzen.
}
Am Ende prüft er dann, ob das sudoku ausgefüllt ist oder nicht und sagt dementsprechend, ob es lösbar ist oder nicht.
//Das macht er aber immer wenn er die funktion durchläuft, und wenn er am ende mal das sudoku ausgefüllt hat, will er wieder zurück, und alte moegliche einträge, die ich noch nicht verwendet habe, auch mal ausprobieren.
|
|
|
21.11.2011 00:07 |
|
|
|
