====== Sudoku-Löser ======

{{ .:sudoku2.png?270|}}
{{ .:sudoku.png?270|}}

Das Logikrätsel Sudoku dürften den meisten Menschen ein Begriff sein. Es geht darum, die Zahlen 1-9 in einem 9x9 Feld unterzubringen. Bei der Anordnung der Zahlen gilt: Weder in einer **Zeile**, noch in einer **Spalte**, noch in einem **3x3 Feld** darf zweimal dieselbe Zahl auftauchen. 

Das erste der rechts zu sehenden Sudokus ist eine Vorlage, bei der bereits ein paar Zahlen vorgegeben sind. Das zweite Bild zeigt dann die dazugehörige Lösung. Alle roten Zahlen wurden auf Basis der vorgegebenen schwarzen Zahlen hinzugefügt.

Auch Sudokus lassen sich wunderbar mittels einfachem Backtracking durch Ausprobieren aller möglichen Kombinationen lösen. Tatsächlich gibt es bei Sudokus noch einige andere Möglichkeiten, eine Lösung auch deutlich "intelligenter" und zeitsparender zu finden. Grundsätzlich genügt aber das Backtracking.

===== Algorithmus =====

**Vorüberlegungen:**
  * In der nachfolgend gegebenen {{ .:sudoku.zip |Vorlage}} wird das Spielfeld in einem 81 Zeichen langen eindimensionalen int-Array namens ''spielfeld'' gespeichert. Das erleichtert wieder u. a. das rekursive Befüllen des nächsten Feldes. Man kann sich das Spielfeld bezüglich der Indizes also wie folgt vorstellen:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
| 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |
| 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 |
| 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 |
| 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 |
| 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |

  * Da es beim Sudoku in der Regel nur um das Finden einer einzigen Lösung geht, muss der rekursive Algorithmus aktiv abgebrochen werden. Ansonsten würde das Programm (wie bei den 8-Damen und den magischen Quadraten) immer noch weitere denkbare Lösungen suchen. Daher steht die boolean-Instanzvariable ''loesungGefunden'' zur Verfügung.
  * Beim Start des Sudoku-Lösers werden leeren Zellen (bei denen kein Startwert vorgegeben war) als ''0'' im ''spielfeld'' gespeichert.

{{:aufgabe.png?nolink  |}}
=== (A1) === 

  - Lade die {{ .:sudoku.zip |Vorlage}} herunter und mache dich rudimentär mit der Funktionsweise des Programms / der GUI vertraut. Du musst den bereits vorgegebenen Code **nicht** nachvollziehen.
  - Du kannst in der GUI einzelne Zahlen vorgeben und dann auf den Knopf "Lösen" klicken. Daraufhin wird die Methode ''loeseSudoku(0)'' aufgerufen.
  - Implementiere diese Methode ''loeseSudoku(int feld)'' sowie die Methode ''istFehlerfrei()''. Nachfolgend findest du Tipps in Form von Pseudocode sowie Lösungsvorschläge.

++++ Pseudocode Löse-Algorithmus |
<code java>
loeseSudoku(feld):
    wenn feld < 81:
        // wenn das Feld bereits vorbelegt ist: überspringen
        wenn spielfeld[feld] nicht 0:
            loeseSudoku(feld+1)
            return
        
        für i von 1 bis 9:
            setze die Zelle 'feld' in spielfeld auf i
            
            wenn das spielfeld fehlerfrei ist: // implementiere dazu die separate methode istFehlerfrei()
                loeseSudoku(feld+1)
                wenn loesungGefunden ist true:
                    return

        setze die Zelle 'feld' in spielfeld auf 0 // keine der oberen Zahlen war erfolgreich, es geht wieder eine Zelle zurück
        
    sonst:
        zeigeErgebnis()
        loesungGefunden = true
</code>
++++

++++ Lösungsvorschlag loeseSudoku()| 
<code java>
if (feld < 81) {
    // wenn das Feld bereits vorbelegt ist: überspringen
    if (spielfeld[feld] != 0) {
        loeseSudoku(feld+1);
        return;
    }

    for (int i = 1; i <= 9; i++) {
        // setze die nächste Zahl ins Feld
        spielfeld[feld] = i;

        // wenn das Spielfeld fehlerfrei ist dann gehe zum nächsten Feld
        if (istFehlerfrei()) {
            loeseSudoku(feld+1);
            if (loesungGefunden) {
                return;
            }
        }
    }
    // es ist keine der oberen Zahlen -> Feld auf 0 setzen
    spielfeld[feld] = 0;
}
else {
    zeigeErgebnis();
    loesungGefunden = true;
}
</code>
++++

++++ Lösungsvorschlag istFehlerfrei() |
<code java>
// überprüfe die Zeilen
for (int beginn = 0; beginn < 81; beginn += 9) {
    // überprüfe die jeweils nächsten 9 Felder auf Dopplungen
    for (int i = beginn; i < beginn+8; i++) {
        for (int j = i+1; j < beginn+9; j++) {
            // wenn zwei Felder identisch (aber nicht 0) sind, dann gibts nen Fehler
            if (spielfeld[i] != 0 && spielfeld[i] == spielfeld[j]) {
                return false;
            }
        }
    }
}

// überprüfe die Spalten
for (int beginn = 0; beginn < 9; beginn++) {
    // überprüfe das jeweils 9-te Feld auf Dopplung
    for (int i = beginn; i < 72; i += 9) {
        for (int j = i+9; j < 81; j += 9) {
            if (spielfeld[i] != 0 && spielfeld[i] == spielfeld[j]) {
                return false;
            }
        }
    }
}

// überprüfe die 3x3-Blocks
int[] blockStartIndices = {
        0, 3, 6,
        27, 30, 33,
        54, 57, 60
    };
for (int beginn : blockStartIndices) {
    // speichere die werte eines blocks in einem temporären Array
    int[] block = new int[9];
    for (int i = 0; i < 9; i++) {
        int zeile = (i / 3) * 9;
        int spalte = i % 3;
        block[i] = spielfeld[beginn + zeile + spalte];
    }

    for (int i = 0; i < 8; i++) {
        for (int j = i + 1; j < 9; j++) {
            if (block[i] != 0 && block[i] == block[j]) {
                return false;
            }
        }
    }
}

return true;
</code>
++++