Autor Beitrag
GuaAck
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 283
Erhaltene Danke: 25

Windows 8.1
Delphi 7 Pers.
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 491
Erhaltene Danke: 188

W7
Delphi 6 pro
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 491
Erhaltene Danke: 188

W7
Delphi 6 pro
BeitragVerfasst: Di 09.01.18 17:27 
GuaAck
Meine Lösung
Einloggen, um Attachments anzusehen!
_________________
Fietes Gesetz: use your brain (THINK)

Für diesen Beitrag haben gedankt: LINUS19
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1623
Erhaltene Danke: 225

WIN7,PuppyLinux
FreePascal,Lazarus,TurboDelphi
BeitragVerfasst: Di 09.01.18 20:04 
Hallo,

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

Gruß Horst
Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: LINUS19
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1525
Erhaltene Danke: 212


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 09.01.18 22:27 
user profile iconLINUS19 hat folgendes geschrieben Zum zitierten Posting springen:
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1525
Erhaltene Danke: 212


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mi 10.01.18 00:58 
user profile iconLINUS19 hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1525
Erhaltene Danke: 212


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mi 10.01.18 21:42 
user profile iconLINUS19 hat folgendes geschrieben Zum zitierten Posting springen:
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: Mi 10.01.18 23:44 
Ich komme jetzt auch auf 9734 Lösungen. Mein Programm hat dafür 34sec. gebraucht.

LG
LINUS19