Anzahl Mögliche Lösungen Sudoku

[Franzose]

Hallo,

ich sitze die ganze Nacht schon an einem nicht spezifischen PHP-Problem.

Ich muss Sudoku-Felder automatisch lösen.
Das ist soweit kein Problem mit Backtracking/Rekursion.
Ich geh einfach für jedes noch nicht ausgefülltes Feld durch und Teste ob eine Ziffer 1-9 allen Sudoku-Kriterien entspricht.
Falls ja rufe ich rekursiv das nächste Feld auf und teste es durch. Usw .... . Falls in diesem Durchlauf es keine Lösung gibt, wird rückwirkend wieder alles auf 0/leer gesetzt und es gibt keine Lösung.

Nun muss ich aber auch noch die maximale Anzahl der Lösungen für ein Sudoku ermitteln. Da fehlt mir aber jetzt total das Konzept.
Ich komm einfach nicht darauf, wie ich das Problem lösen könnte.

Hätte vlt. jemand von euch eine Idee?

Vielen Dank

[erc]

Du verwendest doch schon Backtracking, statt bei einem Ergebnis abzubrechen zählst du das und machst weiter. (Eindeutigkeit beachten) Problem dabei wird sein das das sehr lange dauert. Ich denke da ist aber großes Optimierungspotential. Wenn ich mich nicht täusche gibt es für logisch Lösbare Sudokus nur eine Lösung. Also lös das Sudoku soweit es geht logisch und fang erst dann an zu raten wenn es sein muss.

[Franzose]

Vielen Dank für deinen Tipp.
Nur hätte ich dazu eine Frage.

Folgender Code ist zwar in Java, dürfte aber soweit ok sein.
Ich löse das Sudoku durch versuchen.
Funktion "testeFeld" prüft nur ob der Wert an dieser Stelle erlaubt ist.

Bei Bedarf PN 

Die nicht ausgefüllten Felder sind in meinem Sudoku mit 0 belegt.

Wenn ich dich richtig verstehe müsste ich in der folgende Codestelle nicht true zurückgeben.

Bei Bedarf PN 

Das Problem ist ja in meinem Fall, dass ich bei einem weiteren Durchgang genau die selbe Lösung wieder bekommen würde.
Ich komm nicht drauf, wie ich die erste Lösung ausschließen kann?
Damit ich die nächste Lösung ermitteln kann.

Folgendes Sudoku hat z.B. 4-Lösungen

Bei Bedarf PN 

[ChrisvA]

Ich würde zunächst mal das ganz "logisch" angehen, also alle Zahlen eintragen die eindeutig sind.
Erst wenn dein Algothmus mit Logik nicht mehr weiter kommt würde ein Feld raten. Dann wieder alle möglichen Felder mit Logik ausfüllen, ....

PS: Was bedeutet der Rückgabewert der Funktion? Das das Feld gelöst wurde?

[Franzose]

Hallo ChrisvA und Danke für deine Antwort.

Ja die Funktion gibt true zurück, falls ein Ziffern-Feld korrekt ist.
Die Laufzeit an sich ist jetzt erst mal nicht mein Problem, daher würde ich die Lösungsmethode der Funktion durch ausprobieren nicht ändern.

Oder hilft mir dein Tipp mit logischer Lösung, bei der Ermittlung der Anzahl der möglichen Lösungen?

Vielen Dank und Gruß

[erc]

Das Problem ist ja in meinem Fall, dass ich bei einem weiteren Durchgang genau die selbe Lösung wieder bekommen würde.
Ich komm nicht drauf, wie ich die erste Lösung ausschließen kann?

Du darfst die Funktion nicht verlassen wenn du EINE gültige Lösung gefunden hast, sondern nur wenn du KEINE gültige Lösung gefunden hast.

Das

if(loeseFeld(feld, i+1 ,j)){
      return true;
} 

gegen das

loeseFeld(feld, i+1 ,j); 

ersetzen.

Und wenn ein Feld komplett ist musst du das zählen. Dazu packst du in den Funktionskopf noch ein Zähler und verwendest den als Rückgabewert.

Sollte am ende so aussehen:

    public static boolean loeseFeld(int[][] feld, int i, int j, int solutions){

        //Am Ende der Zeilen angekommen?
        if(i == 9){
            i = 0; //Vom Zeilenanfang anfangen
            if (++j == 9) //Spalte erhöhen um eins und prüfen ob am Ende
                return solutions+1; //Unten rechts angekommen
        }
        
        //Bereits befüllte Felder überspringen und nächstes Feld bearbeiten
        if(feld[i][j] != 0){
            return loeseFeld(feld, i+1 ,j, solutions);
        }
        
        //Mögliche Werte von 1-9
        for(int value = 1; value <= 9; value++){
            
            feld[i][j] = value; //Wert setzen
            
            //Wert auf Gültigkeit prüfen
            if(testeFeld(feld, i, j)){
        loeseFeld(feld, i+1 ,j, solutions);
            }
        }
        
        //Wert wieder zurücksetzen, da kein gültiger Durchlauf
        feld[i][j] = 0;
        
        return solutions;           
    } 

[Franzose]

Hallo erc,

danke für deine Lösung. Ich hab gerade selber eine Lösung gefunden.

Bei Bedarf PN 

Wenn ich unten rechts angekommen bin, gebe ich einfach false zurück.
Also ich führe das Backtracking erneut aus.
Zusätzliche zähle ich die gefunden Lösungen mit einem counter.

Vielen Dank für eure Hilfe

[ChrisvA]

Nur mal aus Neugierde, wie lange dauert es, bis du die Lösungen gezählt hast?

[Franzose]

Das poste ich dir heute Abend/Nacht.

Gruß

[Franzose]

So ein wenig später als gewollt, aber hier ein paar Messungen.

Laufzeit: 2387210 Nanosekunden
Laufzeit: 0.00238721 Sekunden
Anzahl Lösungen:0

Laufzeit: 23405533 Nanosekunden
Laufzeit: 0.023405533 Sekunden
Anzahl Lösungen:4

Laufzeit: 5936458 Nanosekunden
Laufzeit: 0.005936458 Sekunden
Anzahl Lösungen:4

Laufzeit: 8996561 Nanosekunden
Laufzeit: 0.008996561 Sekunden
Anzahl Lösungen:51

Laufzeit: 31310 Nanosekunden
Laufzeit: 3.131E-5 Sekunden
Anzahl Lösungen:0

Das ganze hängt also stark vom jeweiligen Sudoku ab.

[ChrisvA]

Ich hatte erheblich höhere Zeiten erwartet.

[lstegelitz]

Bitte editiere zukünft nicht deinen Code aus den Posts heraus... das macht den gesamten Thread für die Zukunft nutzlos.

Andere mit dem gleichen oder einem ähnlichen Problem sollen auch etwas davon haben.