Kannst du mir was zu Backtracking erzählen? Backtracking = zurück suchen ?? Ich würd mir drunter vorstellen, dass man alle Schritte irgendwie speichert und dann rückgehen schaut, ob das ganze funktionieren kann.
Grob beschrieben ist das Backtracking. Man trifft Entscheidungen, und wenn man an einen Widerspruch/Fehler gerät, ändert man eine (normalerweise die letzte) Entscheidung und probiert dann weiter. Wikipedia hat auch nen eigenen Eintrag dazu.
Auf Sudoku angewand würde das ca. so aussehn (der Einfachheit halber rekursiv beschrieben):
Code:
SetzeFeld(i)
Wenn i > Size*Size
return true; //Abbruchbedingung
GültigeEntscheidungen = {1..Size}
solange Anzahl(GültigeEntscheidungen) > 0
Wähle zufällige, gültige Entscheidung x //(z.B. x=3, d.h. ins i-te Feld wird eine 3 geschrieben)
Wenn EntscheidungGültig(i, x) //x ist auf dem i-ten Feld gültig
Setze(i, x)
Wenn SetzeFeld(i+1) //Probieren, das restliche Sudoku zu füllen
return true; //Sudoku konnte gefüllt werden, also Funktion "erfolgreich" beenden
Entferne x aus GültigeEntscheidungen //Weil x keine gültige Entscheidung war
return false //keine Gültige Entscheidung gefunden, also muss in den vorherigen Feldern was geändert werden
Das ist dann eine sehr einfache Implementierung von Backtracking. Dadurch, dass man Rekursion anwendet, muss man auch nicht ehemalige Entscheidungen speichern, bzw. der Compiler&Stack erledigen das für einen.
Wie schnell dieser Code dann läuft hängt sehr davon ab, wie man die Gültigkeit einer Entscheidung überprüft. Diese muss natürlich false zurückgeben, (genau dann) wenn die Zahl nicht gültig ist. Hier ist aber bspw. auch bereits viel Optimierungs-Potential drin. Im weiter oben genannten Beispiel könnte die Funktion auch bereits erkennen, dass die 1 im 7. Feld nicht gültig ist. Hierfür können dann die verschiedensten Methoden zum Einsatz kommen.
greetz
Mike