Sudoku mehrere Lösungen

J

Java xyrse123

Bekanntes Mitglied
Hallo,
Ich habe ein Programm gemacht das ein Sudoku rekursiv mit Backtracking löst.
Dabei wird aber nur eine Lösung ausgegeben. Ich würde gerne noch einen Zähler einbauen der die Anzahl der Lösungen angibt.
Wie könnte ich die Anzahl aller Lösungen bestimmen?
 
Wenn dein Algorithmus nach der ersten Lösung abbricht dann brauchst du auch keinen Zähler einbauen.. du wirst immer nur eine Lösung bekommen.
Schreib dein Algorithmus doch erstmal so um dass er dir alle Lösungen generiert und ausgibt. Danach kannst du immer noch mit einem Zähler mitzählen wie viele Lösungen es sind.
 
Pauschal gesagt musst du jede Möglichkeit ausprobieren. Wenn du eine Möglichkeit gefunden hast darfst du nicht abbrechen sondern dein Algo muss sich erneut aufrufen / weiter machen.
Das kommt aber auch ein bisschen drauf an wie dein Algo funktioniert / aufgebaut ist.
 
Hier ist meine Lösemethode:
Java: 
static boolean solve(int i, int j, int Matrix[][]) {
        aufrufe++;
        if (i == 9 && j == 8)
            return true; // rechtes unteres Feld erreicht,abbruch

        if (i == 9) { // Eine Zeile weiter nach unten
            i = 0;
            j++;
        }

        if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden           
            return solve(i + 1, j, Matrix); // -> gehe einen Schritt weiter
        }

        for (int value = 1; value <= 9; value++) { // Alle Zahlen von 1-9 werde getestet
            if (check(i, j, value, Matrix) == true) { // Gehe auf nächstes freies Feld
                Matrix[i][j] = value; // setze den Wert
                if (solve(i + 1, j, Matrix) == true)                   
                    return true;           
            }
        }
        Matrix[i][j] = 0; // Feld wird auf Null gesetzt(backtrack)
        return false;
    }
Dann müsste ich die oberste Abbruchbedingung ändern. Die Lösemethode muss dann ja immer weiter aufgerufen werden, um neue Lösungen zufinden, aber was ist dann die Abbruchbedingung dafür?
 
Java xyrse123 hat gesagt.:
Hier ist meine Lösemethode:
Java: 
static boolean solve(int i, int j, int Matrix[][]) {
        aufrufe++;
        if (i == 9 && j == 8)
            return true; // rechtes unteres Feld erreicht,abbruch

        if (i == 9) { // Eine Zeile weiter nach unten
            i = 0;
            j++;
        }

        if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden          
            return solve(i + 1, j, Matrix); // -> gehe einen Schritt weiter
        }

        for (int value = 1; value <= 9; value++) { // Alle Zahlen von 1-9 werde getestet
            if (check(i, j, value, Matrix) == true) { // Gehe auf nächstes freies Feld
                Matrix[i][j] = value; // setze den Wert
                if (solve(i + 1, j, Matrix) == true)                  
                    return true;          
            }
        }
        Matrix[i][j] = 0; // Feld wird auf Null gesetzt(backtrack)
        return false;
    }
Dann müsste ich die oberste Abbruchbedingung ändern. Die Lösemethode muss dann ja immer weiter aufgerufen werden, um neue Lösungen zufinden, aber was ist dann die Abbruchbedingung dafür?
Zum Vergrößern anklicken....

Also deine Methode zählt nicht die Lösungen die möglich sind sondern nur die Aufrufe von der Methode.
Schon mal mein Beispiel dir angeschaut?

Grüße
 
Dein Beispiel habe ich mir angesehen, aber es war mir zu kompliziert und ich habe es nicht wirklich verstanden.
Ich weiß das ich mit der Variable "aufrufe", nur die Anzahl der Aufrufe der Methode und nicht nicht die Anzahl der Lösungen bestimme.
Ich hatte die solve() nur gepostet damit mir vielleicht jemand einen Ansatz gibt, wo ich etwas verändern müsste damit ich die Anzahl aller Lösungen bestimmen kann.
 
Java xyrse123 hat gesagt.:
Dann müsste ich die oberste Abbruchbedingung ändern. Die Lösemethode muss dann ja immer weiter aufgerufen werden, um neue Lösungen zufinden, aber was ist dann die Abbruchbedingung dafür?
Zum Vergrößern anklicken....
Es gibt doch eine Stelle, an der du weisst, dass du eine Lösung gefunden hast. Dort kannst du deinen Zähler erhöhen und dem Aufrufer "vortäuschen", dass keine Lösung gefunden wurde. Das heisst, du musst nicht die Abbruchbedingung ändern, sondern die Information, die du zurück lieferst.
 
Ich habs denke ich einigermaßen verstanden, aber wenn ich folgendes ändere wird das Sudoku unverändert ausgegeben.
Code: 
static int anzahl=0;

static boolean solve(int i, int j, int Matrix[][]) {
if (i == 9 && j == 8) {           
            anzahl++;                    
        }
       
    if(anzahl<=1 ) {         
        return true; // Sudoku eindeutig
    }
}
 
Wenn ich nur folgendes ändere kann ich es aber nicht lösen, oder meintest du was anderes?
Code: 
static int anzahl=0;

static boolean solve(int i, int j, int Matrix[][]) {
if (i == 9 && j == 8) {           
                anzahl++;       
            return false; 
       
        }
 }
 
Nein, könnte es daran liegen das in der Mainmethode das hier steht:
Code: 
if (solve(0, 0, Matrix) == true) // wenn Sudoku lösbar ->
            print(Matrix); // wird es ausgegeben

        else
            System.out.println("Keine Lösung");
Es wird halt immer "keine Lösung" ausgegeben wie ich weiter oben schon geschrieben hatte.
Edit: Wenn ich das mit dem if wegnehme wird nur das ungelöste Sudoku gedruckt
 
Wenn ich die Ausgabe so mache, wird auch nur das unausgefüllte Sudoku gedruckt.
In der der solve() Methode wird doch auch nirgendwo true zurückgegeben.
Code: 
solve(0, 0, Matrix);
print(Matrix);
 
Java xyrse123 hat gesagt.:
Wenn ich die Ausgabe so mache, wird auch nur das unausgefüllte Sudoku gedruckt.
In der der solve() Methode wird doch auch nirgendwo true zurückgegeben.
Zum Vergrößern anklicken....
Ja. Natürlich. Es ist doch gerade der "Trick" an der Sache, dass jede gefundene Lösung "verworfen" wird, damit weiter gesucht wird. Also ist die Matrix zum Schluß wieder in ihrem Ausgangszustand. Das sagt aber nichts darüber aus, ob in der Zwischenzeit alle Lösungen korrekt gefunden wurden oder ob noch etwas falsch ist. Warum gibst du die Matrix nicht einfach mal bei jeder Lösung aus und siehst dir an, ob es korrekt ist?
 
Achso.
Code: 
int anzahl=0;
solve(...){
If(i==9 && j==8) {
anzahl++;
print(Matrix);
System.out.println(anzahl);
return false;
}
}
 
Jetzt ist doch noch ein Problem aufgetreten.
Ich habe ein Sudoku eingegeben und es hat mir angezeigt das es 2 Lösungen gibt, aber es wurden 2 Mal die gleiche Lösung ausgegeben.

Edit: Es wurden nur 2 Zahlen vertauscht, hat sich geklärt.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Java Sudoku toString für Sudoku Feld überschreiben
Antworten: 14
Sudoku: Laden / Speichern von Zahlen aus/in mehrere JTextFields aus/in eine(r) Textdatei
Antworten: 9
Übungsaufgaben mit Lösungen
Antworten: 5
Lösungen zu einem Lückentext finden
Antworten: 0
"Javakurs Freitagsrunde" - Lösungen
Antworten: 6

Zurück
Oben