Im Unterricht haben wir die Backtrackingstrategie aus dem Damenproblem in eine allgemeinere Form gepackt und zusätzlich noch Kriterien für ein Backtrackingproblem aufgestellt. Die aufgestelle Methodik, ein Problem mit Backtracking zu lösen, haben wir dann auf das automatische Lösen eines Sudokus angewandt.

Prinzip Sudoku

Bei Sudoku handelt es sich in den meisten Fällen um ein Feld mit 9 x 9 Kästchen.

Wie im obigen Bild zu sehen, wird das 9 x 9 Feld nocheinmal in 3 x 3 Felder aufgeteilt. In jedem dieser kleineren Felder dürfen die Zahlen von 1-9 nur einmal vorkommen. Gleiches gilt für jede Reihe sowie Spalte.

Ziel des Spieles ist es nun, dass man ein schon angefangenes Rätsel löst.

Ein ungelöstes Sudoku

Ein gelöstes Sudoku

Kriterien

Folgende Kriterien helfen bei der Beurteilung, ob ein Problem durch Backtracking gelöst werden kann:

1. Ein Problem kann in unterschiedliche Teilprobleme unterteilt werden
2. Jedes Problem hat verschieden Möglichkeiten, mit denen es gelößt werden kann.
3. Für die Lösungen der Teilprobleme müssen Abbruchbedingungen bestehen

Diese Kriterien lassen sich beispielsweise bei dem Sudoku-Problem untersuchen:

1. Eine Teilproblem wird durch jedes Feld, dass noch keine Zahl hat beschrieben.
2. Auf ein Feld kann jede Zahl von 1-9 gesetzt werden, so lange sie nicht schon in der Reihe oder Spalte sowie 3 x 3 Quadrat gesetzt wurden.
3. Sollte keine Zahl mehr auf ein Feld gesetzt werden, so ist die Abbruchbedingung erfüllt.

Wir erkennen also, dass alle drei Kriterien bei dem vorliegendem Problem erfüllt wurden.

Pseudocode

Für jedes Backtracking Problem lässt sich ein allgemeiner Pseudocode formulieren:

backtrack()
    FALLS Lösung gefunden
        GIB Lösung ZURÜCK
    finde ungelöstes Teilproblem
    DURCHLAUFE ALLE Möglichkeiten
        FALLS Möglichkeit zulässig
            führe Möglichkeit aus
        FALLS backtrack() eine Lösung zurückgibt
            GIB Lösung ZURÜCK
        mache Möglichkeit rückgängig
    GIB keine Lösung ZURÜCK

Der im Unterricht bei Herrn Leiß erstellte Code geht wie schon beim Damenproblem nach folgendem Prinzip vor:

1. Überprüft, ob die Basis erfüllt wurde. Dies tritt ein, wenn das Problem vollständig gelößt wurde und alle Teillösungen für die Lösung gefunden wurden. Es kann nun die gefundene Lösung zurückgegeben und die Methode abgebrochen werden.

2. Wurde das Problem noch nicht gelößt, so findet man das erste Teilproblem und versucht dieses zu lösen.

3. Dabei werden für dieses Problem alle Möglichkeiten es zu lösen nacheinander gesetzt und dann wird für die jeweilige Möglichkeit überprüft, ob das Gesamtproblem gelößt werden kann. Kann das Problem gelößt werden, so wird die Lösung zurückgegeben

4. Andernfalls wird die gerade Überprüft Möglichkeit wieder rückgängig gemacht und die nächste Möglichkeit wird behandelt.

5. Sollte keine Lösung für das aktuelle Teilproblem vorliegen, wird keine Lösung zurückgeben.

Für die später folgenden Implementierung in das bereitgestellte Raster wird der allgemeine Code in einen spezifischeren Code, der auf das Sudokuproblem passt, umgewandelt.

backtrack()
    FALLS alle Felder mit Zahl
        GIB Lösung ZURÜCK
    finde Feld ohne Zahl
    DURCHLAUFE ALLE Zahlen (1-9)
        FALLS Zahl zulässig
            setze Zahl
        FALLS backtrack() eine Lösung zurückgibt
            GIB Lösung ZURÜCK
        mache Zahl setzen rückgängig
    GIB keine Lösung ZURÜCK

Implementierung

Zum Schluss kann man dann den oben abgebildeten Code in das Raster Implementieren:

public String findOneSolution(SudokuListener listener, int millisecDelay) {
    if(getNextFreePos() == null) return toString(); //Abbruchbedingung
    Pos p = getNextFreePos();   //Finde erstes Teilproblem
    
    for(int i = 1; i < 10; i++){    //Alle Möglichkeiten des Teilproblems
      if(isValidCandidate(p,i)) {   
        setFieldValue(p, i, listener, millisecDelay);  
        if (findOneSolution(listener, millisecDelay) != null) return toString(); //Gib Lösung zurück
      }
      setFieldValue(p, 0, listener, millisecDelay);
    }
    
    return null; // Gib keine Lösung zurück
  }