Ankündigung

Einklappen
Keine Ankündigung bisher.

Anzahl Mögliche Lösungen Sudoku

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Anzahl Mögliche Lösungen Sudoku

    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


  • #2
    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.

    Kommentar


    • #3
      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.

      PHP-Code:
      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.

      PHP-Code:
      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

      PHP-Code:
      Bei Bedarf PN 

      Kommentar


      • #4
        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?
        mysql ist veraltet Mails senden: Ohne Probleme und ohne mail()
        PHP-Code:
        echo 'PS: <b>Meine Antwort ist keine Lösung, sondern nur eine Hilfe zur Lösung.</b>'

        Kommentar


        • #5
          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ß

          Kommentar


          • #6
            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
            PHP-Code:
            if(loeseFeld(feldi+,j)){
                  return 
            true;

            gegen das
            PHP-Code:
            loeseFeld(feldi+,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:
            PHP-Code:
                public static boolean loeseFeld(int[][] feldint iint jint solutions){

                    
            //Am Ende der Zeilen angekommen?
                    
            if(== 9){
                        
            0//Vom Zeilenanfang anfangen
                        
            if (++== 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(feldi+,jsolutions);
                    }
                    
                    
            //Mögliche Werte von 1-9
                    
            for(int value 1value <= 9value++){
                        
                        
            feld[i][j] = value//Wert setzen
                        
                        //Wert auf Gültigkeit prüfen
                        
            if(testeFeld(feldij)){
                    
            loeseFeld(feldi+,jsolutions);
                        }
                    }
                    
                    
            //Wert wieder zurücksetzen, da kein gültiger Durchlauf
                    
            feld[i][j] = 0;
                    
                    return 
            solutions;           
                } 

            Kommentar


            • #7
              Hallo erc,

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

              PHP-Code:
              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

              Kommentar


              • #8
                Nur mal aus Neugierde, wie lange dauert es, bis du die Lösungen gezählt hast?
                mysql ist veraltet Mails senden: Ohne Probleme und ohne mail()
                PHP-Code:
                echo 'PS: <b>Meine Antwort ist keine Lösung, sondern nur eine Hilfe zur Lösung.</b>'

                Kommentar


                • #9
                  Das poste ich dir heute Abend/Nacht.

                  Gruß

                  Kommentar


                  • #10
                    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.

                    Kommentar


                    • #11
                      Ich hatte erheblich höhere Zeiten erwartet.
                      mysql ist veraltet Mails senden: Ohne Probleme und ohne mail()
                      PHP-Code:
                      echo 'PS: <b>Meine Antwort ist keine Lösung, sondern nur eine Hilfe zur Lösung.</b>'

                      Kommentar


                      • #12
                        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.
                        Über 90% aller Gewaltverbrechen passieren innerhalb von 24 Stunden nach dem Konsum von Brot.

                        Kommentar

                        Lädt...
                        X