Hallo Delphi-Laie,

stimmt, das war im Jahrgang 2012 des Spektrum. Die Aufgabe ist im Anhang. Genau diese Aufgabe kann mein Programm nicht lösen. Und diese Aufgabe braucht auch mit dem Proggramm von Linus die mit Abstand größte Anzahl von Solve-Aufrufen.

Als ich das Programm gemacht habe, da ging es mir nicht um Brute-Force. Ich wollte wissen, ob meine Lösungsmethode immer zum Erfolg führt. Wenn ich eine Aufgabe nicht lösen kann, dann kann das daran liegen, dass ich eine Kombination einfach nicht sehe, oder daran, dass meine Lösungsmethode bei der Aufgabe nicht zum Ziel führt. Bei der angeführten Aufgane aus dem Spektrum 2012 kam ich mit logischen Schließen nicht weiter und musste probieren. Mein Programm bestätigte, dass ich nichts übersehne habe.

Viele Grüße
GueAck

Dieses Sudoku,was ich gemacht habe braucht sogar 6.967.860 Aufrufe.
000040000
180037000
500010000
700054000
000000080
000000090
000970000
200000000
009300000
---------------------
|9 2 6 |5 4 8 |1 3 7
|1 8 4 |2 3 7 |5 6 9
|5 3 7 |6 1 9 |8 4 2
---------------------
|7 9 2 |8 5 4 |6 1 3
|3 1 5 |7 9 6 |2 8 4
|4 6 8 |1 2 3 |7 9 5
---------------------
|6 4 1 |9 7 2 |3 5 8
|2 5 3 |4 8 1 |9 7 6
|8 7 9 |3 6 5 |4 2 1
Lösungszeit: 556 Millisek.
6967860

Moin GuaAck,
das Beispiel habe ich ich mit meinem Programm getestet, es ist nicht eindeutig lösbar!
Bei 8000 Lösungen hab ich es abgebrochen.
SimpleSudoku zeigt dies ebenfalls an.
Ich schätze mal, Dein Programm erwartet eine eindeutige Lösung, was ja auch richtig ist.
Gruß Fiete

Das kann aber eigentlich nicht sein,weil das Sudoku 17 Zahlen hat und damit eindeutig lösbar sein müsste.

Meine Lösung

Hallo,

da bin ich froh, dass Grishnaks Solver auch 9734 Lösungen findet,


Gruß Horst

LINUS19 hat folgendes geschrieben :

Das kann aber eigentlich nicht sein,weil das Sudoku 17 Zahlen hat und damit eindeutig lösbar sein müsste.

Hängt das wirklich nur von der Anzahl der vorgegebenen Zahlen (oder anderweitigen Symbole) ab? Oder vielmehr auch davon, wie diese placiert sind (was ich vermute)?

Stimmt du hast recht, hier ein Zitat das ich gefunden habe:

"Damit weiß man nun also, dass es keine eindeutig lösbaren Sudokus mit 16 oder weniger vorgegebenen Zahlen gibt. Doch schon wartet die nächste große Frage auf die Mathematiker: Wie viele eindeutig lösbare Sudokus mit 17 vorgegebenen Zahlen gibt es nun tatsächlich? "

Dann muss ich wohl meinen Sudoku Löser so erweitern das er auch mehrere Lösungen findet.

Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt.

LINUS19 hat folgendes geschrieben :

Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt.

"Eindeutig lösbar" war wohl unglücklich ausgedrückt. Es kann auch "nur" überhaupt lösbar sein, dann ggf. sogar mehrfach. Daß es Sudokus gibt, die zwar lösbar sind, das aber nicht eindeutig, also mehr als eine Lösung haben, war mir bis dato unbekannt, könnte aber tatsächlich so sein, deshalb mein Formulierungsmangel. Ich krame deswegen aber nicht das Spektrumheft wieder hervor, so sehr interessiert es mich nicht.

LINUS19 hat folgendes geschrieben :

Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt.

Ich muß das noch einmal aufwärmen.

Also, die eindeutige Lösbarkeit ist ja gerade ein Merkmal der Sudokus, denn in ein leeres oder nur unzureichend gefülltes Sudoku lassen sich alle mögliche Lösungen eintragen, doch so etwas zu finden, ist nach meinem Wissen nimmer das Ziel. Sudokus haben so gesehen als Lösungsmenge nur eine Einermenge, aber keine Lösungsmenge i.S.v. mehreren (natürlich endlich vielen) Lösungen.

Soweit ich mich entsinne, war das Sudoku, das ich erwähnte, eben doch eindeutig lösbar, d.h., es hat nur eine Lösung. Je mehr Startzahlen man wegläßt, umso mehr Lösung(en) gibt es tendenziell, irgendwann wächst die Anzahl der Lösungen an und wird größer als 1. 17 Vorgabesymbole sind, so gesehen, wahrscheinlich wirklich die äußerste Schmerzgrenze.

Ich komme jetzt auch auf 9734 Lösungen. Mein Programm hat dafür 34sec. gebraucht.

LG
LINUS19