Autor |
Beitrag |
GuaAck
Beiträge: 376
Erhaltene Danke: 32
Windows 8.1
Delphi 10.4 Comm. Edition
|
Verfasst: Mo 08.01.18 01:16
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
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Delphi-Laie, LINUS19
|
|
LINUS19
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Di 09.01.18 16:15
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
|
|
Fiete
Beiträge: 607
Erhaltene Danke: 342
W7
Delphi 6 pro
|
Verfasst: Di 09.01.18 16:46
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
_________________ Fietes Gesetz: use your brain (THINK)
|
|
LINUS19
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Di 09.01.18 16:53
Das kann aber eigentlich nicht sein,weil das Sudoku 17 Zahlen hat und damit eindeutig lösbar sein müsste.
|
|
Fiete
Beiträge: 607
Erhaltene Danke: 342
W7
Delphi 6 pro
|
Verfasst: Di 09.01.18 17:27
Meine Lösung
Einloggen, um Attachments anzusehen!
_________________ Fietes Gesetz: use your brain (THINK)
Für diesen Beitrag haben gedankt: LINUS19
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 09.01.18 20:04
Hallo,
da bin ich froh, dass Grishnaks Solver auch 9734 Lösungen findet,
Gruß Horst
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: LINUS19
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 09.01.18 22:27
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)?
_________________ Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.
|
|
LINUS19
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Di 09.01.18 22:34
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.
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
LINUS19
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Di 09.01.18 22:45
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.
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Mi 10.01.18 00:58
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.
_________________ Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Mi 10.01.18 21:42
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.
_________________ Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Mi 10.01.18 23:44
Ich komme jetzt auch auf 9734 Lösungen. Mein Programm hat dafür 34sec. gebraucht.
LG
LINUS19
|
|