Sudoku Rekursiv lösen

[Mc Noise]

Hallo,

ich habe ein Programm zum lösen von Sudokus geschrieben. Das logische lösen des Sudoku klappt. Meine Vorgehensweise ist die Folgende, ich habe ein 2d Array mit 9*9 Objekte der Klasse SudokuZelle. Die Klasse hat die Fähigkeit für jede Zelle ungültige Werte auszuschließen, eindeutige Werte und alle noch möglichen Werte der einzelnen Zelle zu liefern.

Durch das Ausschließen der Werte erhalte ich eine Kandidatenliste für jede Zelle.
Jetzt möchte ich auch Sudokus lösen, bei dennen es keinen eindeutigen Werte für jede Zelle gibt.

Eine Methode zur Überpüfung, ob das Sudoku wiederspruchsfrei gelöst ist habe ich, das systematische durchprobieren der Kandidatenliste bereitet mir allerdings Kopfzerbrechen.

Danke schonmal für eure Hilfe.

 

[Kekzii]

Sudoku ist/kann ein kompliziertes Spiel sein...

wenn es keine eindeutigen Werte gibt dann ist das pures ausprobieren 😉 heisst du müsstest jede möglichkeit ausprobieren und auf ihre Richtigkeit prüfen

also erst alle eindeutigen Felder ausfüllen und wenn keine eindeutigen Felder mehr übrig sind ausprobieren ansonsten kann es sehr schwer werden einem Programm so ein logisches denken zu vermitteln das es richtig lösen kann 😉

 

[nrg]

Backtracking ? Wikipedia wäre da afaik das mittel zum zweck. habs aber noch nie selbst implementiert..

 

[Mc Noise]

Hallo,

so hab ich mir das auch gedacht, mein Problem ist das Entwickeln einer Methode, welche systematisch meine Kanditaten für jede Zelle durchprobiert.

 

[nrg]

genau. hier ist die sequenzielle vorgehenweiße anhand vom "Acht-Damen-Problem" sehr schön zu sehen:
(quelle: wikipeidia)

sieht glaub schlimmer aus, als es ist. wird halt ne ziehmlich große iteration, die auch gern mal einige zeit in anspruch nehmen kann.

 

[Kekzii]

gehts nicht iwie mit ner For-schleife? aber bestimmt sehr langsam..

for (int h = 0; h<feld.length;h++{
      for (int i = 0; i<feld.length;i++) {
           for (int j = 0; j<feld.length; j++){
                if (feld[i][j] == feld[h][i]){
                   ergebnis =false;
                 }
            }
        }
    }

oder so in der art 🙂 keine ahnung obs klappen würde

 

[Gast2]

Hi,
ich hab auch mal nen SodukoSolver geschrieben. (falls du den ganzen code haben willst sag bescheid).
So in etwa habe ich das implementiert:

- Zuerst alle freien Stellen im Sudoku bestimmen und in einer Liste speichern.
- Danach rekursiv diese Stellen durchlaufen und für jede Stelle die Zahlen 1-9 durchprobieren.
- Wenn alle Stellen ausgefüllt sind und das Sudoku gültig ist, dann hast du eine Lösung gefunden.

Mal nen kleines beispiel:
Du setzt für die Stelle 1 die Zahl 1 ein. Nun prüfst du ob diese Zahl gültig ist, d.h. Spalte, Zeile und Box prüfen. Wenn die Zahl nicht gültig ist setzt du die Zahl 2 ein und prüfst wieder. Wenn die Zahl gültig ist machst du an der Stelle 2 weiter.
So durchläufst du den ganzen Lösungsbaum und kommst schlussendlich irgendwann zu deinen Lösungen.

Es gibt dann noch nen paar kniffe mit denen du das ganze noch ein wenig beschleunigen kannst.

 

[Mc Noise]

Genau so ist auch mein Gedankenansatz, nur die Umsetzung macht mir Probleme.
Ich habe nach dem durchführen des Ausschlußverfahrens mehrere Möglichkeiten für die einzelnen Sudokufelder. Würde mir schon reichen wenn er meine möglichen Werte durchprobiert.
Irgendwie fehlt mir die Vorstellung wie das rekursive lösen umzusetzen ist.

Wäre nett wenn du mir deinen Code schicken könntest.

 

[Gast2]

    private boolean solveBacktrack(int position) {
        if (position == missingFieldCount) { // Wenn alle Positionen besetzt sind => Lösung gefunden
            return true;
        }

        Point pos = missingFields.get(position); // missingFields ist ne Liste der freien Felder
        int row = (int)pos.getX();
        int column = (int)pos.getY();

        for (int i = 1; i <= maxNr; i++) {
            if (checkInsertValue(row, column, i)) { // prüft ob die Zahl i an der Stelle (row/column) gültig ist
                gridCalc[row][column] = i;
                if (solveBacktrack(position + 1)) { // wenn es ne Lösung gibt => algo beenden
                    return true;
                }
            }
        }

        // Dieser weg ist keine Lösung
        gridCalc[row][column] = 0;
        return false;
    }

Diese Methode gibt dir die erste mögliche Lösung aus. Lässt sich aber sehr leicht modifizieren, dass er z.b. alle Lösungen in einer Liste sammelt.

 

[Mc Noise]

Hier mal meine Variante vielleicht hat jemand eine Idee wie ich das Backtracking implementieren kann?
[JAVA=42]

public void backtrackingVerfahren()
{
// Wenn das Sudoku geloest ist
if ((checkSumSpalten() && checkSummeZeilen()))
{
sudokuDisplayAusgabe();
System.exit(0);
}
// schließt den gesetzten Wert für die Zellen der Zeile, Spalte und dem Block aus
schliesseUngueltigeWerteAus();

for (int zeile = 0; zeile < sudoku.length; zeile++)
{
for (int spalte = 0; spalte < sudoku[zeile].length; spalte++)
{
// Wenn das Feld leer ist
if (sudoku[zeile][spalte].liefereWert() == 0)
{
// liefert dem nächstmoeglichen Wert oder -1 falls kein naechster Wert moeglich ist
int moeglicherWert = sudoku[spalte][spalte].liefereNaechstMoeglZahl();
// Es gibt einen moeglichen Wert
if (moeglicherWert > 0)
{
// Setzt in das Feld den naechstmoeglichen Wert
sudoku[zeile][spalte].setzeWert(moeglicherWert);
// schließt den gesetzten Wert für die Zellen der Zeile, Spalte und dem Block aus
schliesseUngueltigeWerteAus();
}
// Es gibt für dieses Feld keinen Wert
if(moeglicherWert == -1)
{
// Wiederspruch alle Werte fuer dieses Feld wurden ausgeschloßen
// hier sollte jetzt das Backtrackingverfahren beginnen
}
}
}
}
}



[/code]