Sudoku mehrere Lösungen

[Java xyrse123]

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?

 

[truesoul]

Hallo.

Indem du einen Zähler (int) der Methode mit gibst und dann hochzählst.
Den Wert gibst du dann zurück.

Grüße

 

[JStein52]

Ist denn dein Algorithmus überhaupt darauf angelegt alle Lösungen zu finden oder bricht er nach der ersten gefundenen ab ?

 

[Java xyrse123]

Ja, nach der ersten Lösung bricht der Algorithmus ab, deswegen weiss ich auch nicht wie ich das mit dem Zähle machen soll.

 

[Robat]

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.

 

[Java xyrse123]

Das Problem ist nur das ich nicht weiß wie man mehrere Lösungen finden kann. Wie müsste ich da vorgehen?

 

[Robat]

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.

 

[truesoul]

Hallo.

Hier mal ein Beispiel.

Viel Spaß damit

 

[Java xyrse123]

Hier ist meine Lösemethode:

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?

 

[truesoul]

Hier ist meine Lösemethode:

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?

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

 

[Java xyrse123]

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.

 

[Meniskusschaden]

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?

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.

 

[Java xyrse123]

Ich habs denke ich einigermaßen verstanden, aber wenn ich folgendes ändere wird das Sudoku unverändert ausgegeben.

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
    }
}

 

[Meniskusschaden]

Ich habs denke ich einigermaßen verstanden, aber wenn ich folgendes ändere wird das Sudoku unverändert ausgegeben.

So änderst du ja auch nichts, denn wenn du true zurück lieferst, wird ja nicht weiter gesucht.

 

[Java xyrse123]

Wenn ich return false mache, kommt als Ausgabe "keine Lösung".

 

[Meniskusschaden]

Wenn ich return false mache, kommt als Ausgabe "keine Lösung".

Das kann nicht sein, denn dein Code enthält nirgends so eine Ausgabe.

Ich weiß nicht, warum du so viel geändert hast. Du hättest nur ein Wort ändern müssen (und natürlich den Zähler einbauen).

 

[Java xyrse123]

Wenn ich nur folgendes ändere kann ich es aber nicht lösen, oder meintest du was anderes?

static int anzahl=0;

static boolean solve(int i, int j, int Matrix[][]) {
if (i == 9 && j == 8) {           
                anzahl++;       
            return false; 
       
        }
 }

 

[Meniskusschaden]

Doch, ich würde erwarten, dass das funktioniert. Klappt es denn nicht?

 

[Java xyrse123]

Nein, könnte es daran liegen das in der Mainmethode das hier steht:

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

 

[Meniskusschaden]

Nein, könnte es daran liegen das in der Mainmethode das hier steht:

In der main-Methode kommt natürlich immer false an.

 

[Java xyrse123]

Aber das Sudoku wird ja trotzdem nicht gelöst ausgegeben.

 

[Meniskusschaden]

ber das Sudoku wird ja trotzdem nicht gelöst ausgegeben.

Nein, wenn du die Ausgabe so organisierst natürlich nicht. Ich würde mich aber erst einmal um die eigentliche Kernaufgabe kümmern, nämlich ob alle Lösungen gefunden und korrekt gezählt werden.

 

[Java xyrse123]

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.

solve(0, 0, Matrix);
print(Matrix);

 

[Meniskusschaden]

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.

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?

 

[Java xyrse123]

Danke dir ,es funktioniert jetzt mit allenLösungen finden.
Habe ein Sudoku getestet und es hatte 9734 Lösungen genau wie ein anderer Löser mir auch angezeigt hat.

 

[truesoul]

Danke dir ,es funktioniert jetzt mit allenLösungen finden.
Habe ein Sudoku getestet und es hatte 9734 Lösungen genau wie ein anderer Löser mir auch angezeigt hat.

Hallo.

Das ist doch super.
Wie schaut denn deine Lösung aus?

Grüße

 

[Java xyrse123]

Steht doch schon weiter oben, oder was meinst du?

 

[truesoul]

Steht doch schon weiter oben, oder was meinst du?

Wo steht die Lösung?
Welcher Post?

Ich meine die fertige Implementierung.

Grüße

 

[Java xyrse123]

Achso.

int anzahl=0;
solve(...){
If(i==9 && j==8) {
anzahl++;
print(Matrix);
System.out.println(anzahl);
return false;
}
}

 

[Java xyrse123]

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.