Solver für Extreme Str8ts

Thomas
Posts: 5
Joined: Thursday 21. February 2019, 16:25

Solver für Extreme Str8ts

Post by Thomas » Friday 22. February 2019, 11:35

Nachdem ich auch schon seit längerer Zeit Str8ts löse und oft an den richtig schwierigen Extremes verzweifelt bin, habe ich einen "Str8ts Solver" entwickelt. Ich habe das Thema mit Jeff Widderich und Andrew Stuart diskutiert und ihre Genehmigung zur Nutzung ihrer Rechte erhalten. Seit etwa zwei Wochen ist der Solver im Apple Store online.
https://itunes.apple.com/de/app/str8ts- ... 58653?mt=8
Da der Solver einen einstufigen Backtracking Algorithmus enthält, kann er nahezu alle Extremes lösen. Ich habe erst zwei Str8ts gefunden, bei denen der Solver Unterstützung durch den User benötigt hat. Um noch mehr Beispiele zu haben, suche ich jetzt noch weitere richtig schwierige Str8ts. Vielleicht könntet Ihr mir mal schreiben, welche Str8ts für Euch am Schwierigsten waren. Danke schon mal. Thomas

kodela
Posts: 68
Joined: Thursday 2. July 2015, 23:26

Re: Solver für Extreme Str8ts

Post by kodela » Friday 22. February 2019, 15:39

Hallo Thomas,

ist ja interessant, was Du schreibst. Ich bin eben auch mit einem "Str8ts Solver" fertig geworden. Mein Ansatz ist allerdings ein anderer, wie Deiner. Ich habe vor allem nicht vor, mein Programm in Android umzusetzen. Es ist in Java geschrieben. Du kannst es Dir ja einmal auf meiner Homepage ansehen, allerdings derzeit noch nicht mit dem BackTrackingSolver, lediglich ein LevelLoeser.

Eine Frage würde mich interessieren, gewährleistet Dein Solver, dass erkannt wird, wenn es für ein Str8ts mehr als eine Lösung gibt? Meiner erkennt das noch nicht.

Übrigens, wenn Du extreme Str8ts suchst, dann kannst Du hier eine ganze Menge finden. Doch Vorsicht, bei einigen bin ich mir nicht sicher, ob sie nicht fehlerhaft sind und zwei, die Nummern #005 und #032, sind nach meinen bisherigen Feststellungen identisch.

Gruß, kodela

Thomas
Posts: 5
Joined: Thursday 21. February 2019, 16:25

Re: Solver für Extreme Str8ts

Post by Thomas » Saturday 23. February 2019, 12:17

Hallo Kodela,
ich habe mir Deine Homepage angesehen. Du hast einen tollen Job gemacht und sicher viel Mühe und Arbeit hineingesteckt. Über Algorithmen nachzudenken und diese in Software umzusetzen, macht aber auch Spaß!
Ich glaube, dass sich ein Backtracking Algorithmus in Java nur schwierig vernünftig umsetzen lässt. Nach meinen Erfahrungen würde eine Berechnung, die mit massiver Parallelisierung und optimierten Algorithmen auf dem iPhone in 5 Sekunden abläuft, in Java 100 bis 1000 mal langsamer sein. Ich hatte früher in C++ unter Windows meine ersten Solver programmiert. Aber selbst in C++ unter Windows läuft alles noch viel langsamer als auf dem iPhone.
Meiner Meinung nach muss ein Str8ts immer eine eindeutige Lösung liefern. Wenn es mehrere Lösungsmöglichkeiten gibt, dann ist das Str8ts falsch. Hast Du Str8ts, die mehrdeutig sind?
Danke für den Link. Ich werde die Puzzles alle mal durchlaufen lassen. Leider wird dieses Archiv seit zwei Jahren nicht mehr ergänzt.
Viele Grüße
Thomas

kodela
Posts: 68
Joined: Thursday 2. July 2015, 23:26

Re: Solver für Extreme Str8ts

Post by kodela » Saturday 23. February 2019, 15:53

Thomas wrote: Saturday 23. February 2019, 12:17 Ich glaube, dass sich ein Backtracking Algorithmus in Java nur schwierig vernünftig umsetzen lässt. Nach meinen Erfahrungen würde eine Berechnung, die mit massiver Parallelisierung und optimierten Algorithmen auf dem iPhone in 5 Sekunden abläuft, in Java 100 bis 1000 mal langsamer sein.
Hallo Thomas,

eben war ich mit meiner Antwort fertig und habe sie abgesandt und was sah ich, alles was ich geschrieben hatte, war verschwunden. Lediglich das komplette Zitat von Deiner Antwort war da. Also fange ich noch einmal an:

Deiner Einschätzung zu der unter Java (nicht Java Script!) erreichbaren Geschwindigkeit muss ich doch sehr deutlich widersprechen. Probiere doch einmal mit meinem Sudoku-Programm, ebenfalls unter Java geschrieben, 1000 Sudokus mit dem Level 5 zu erzeugen. Dafür muss der Backtracking Solver etwa 300 mal jede der zu erzeugenden Aufgaben im Durchschnitt etwa 300 mal lösen, bis alles passt. Er wird also etwa 300.000 mal eine Aufgabe lösen. Dafür braucht er bei mit etwa fünf Sekunden. 1000 Sudokus mit dem Level 1 werden sogar deutlich unter zwei Sekunden erzeugt (und in die Liste geschrieben). Das alles habe ich über den Profiler festgestellt.

Und jetzt zu Str8ts. Da ist der BackTrackingSolver bei mir noch in Bearbeitung. Es ist also nur der einfache LevelSolver im Einsatz. Dieser wird für jede zu erzeugende Str8ts Aufgabe mit dem Level 5 etwa 50 und für den Level 1 nur noch 20 Millisekunden. Und Du brauchst auf dem iPhone 5 Sekunden. Wenn das bei mir mit Javo so wäre, würde ich nicht mehr programmieren.

Gruß, kodela

Thomas
Posts: 5
Joined: Thursday 21. February 2019, 16:25

Re: Solver für Extreme Str8ts

Post by Thomas » Saturday 23. February 2019, 20:12

Hallo Kodela,
ich glaube, da hast Du etwas falsch verstanden. Ich habe nicht gesagt, was in den 5 Sekunden berechnet wird.
Unten ein Video mit der Berechnung eines Extreme Str8ts mit zweimal Backtracking (einmal etwa 300 und dann noch etwa 150 Durchläufe). Dazu noch das Protokoll der Berechnung.
Gruß Thomas
http://str8ts.halbritter.org/Str8ts-Gam ... eme888.pdf
http://str8ts.halbritter.org/Str8ts-Gam ... eme888.MP4

kodela
Posts: 68
Joined: Thursday 2. July 2015, 23:26

Re: Solver für Extreme Str8ts

Post by kodela » Saturday 23. February 2019, 22:56

Thomas wrote: Saturday 23. February 2019, 20:12 Hallo Kodela,
ich glaube, da hast Du etwas falsch verstanden. Ich habe nicht gesagt, was in den 5 Sekunden berechnet wird.
Hallo Thomas,

das muss wohl so sein. Wenn mit Deiner Aussage nicht gesagt ist, was in den 5 Sekunden berechnet wird, dann habe ich aber immer noch nicht verstanden, was Du damit sagen wolltest:
Ich glaube, dass sich ein Backtracking Algorithmus in Java nur schwierig vernünftig umsetzen lässt. Nach meinen Erfahrungen würde eine Berechnung, die mit massiver Parallelisierung und optimierten Algorithmen auf dem iPhone in 5 Sekunden abläuft, in Java 100 bis 1000 mal langsamer sein.
Geht es hier nicht um das Lösen extremer Str8ts per Backtracking-Suche?

Ich habe übrigens mit meinem noch nicht ganz fertigen Backtracking Löser die Aufgabe #444 von Dir richtig gelöst. Zumindest bin ich zum selben Ergebnis gekommen wie Du. Da die Lösung im Bruchteil einer Sekunde geliefert wurde, habe ich den Profiler mitlaufen lassen. Das Ergebnis kannst Du hier sehen:

BTS_#444_2.PNG
BTS_#444_2.PNG (36.72 KiB) Viewed 12863 times

Wie Du siehst, hat mein Loeser insgesamt 290 ms bei 77 Durchläufen benötigt. Für die eigentliche Backtracking-Arbeit fielen lediglich 0,892 ms an.

Was ich noch fragen wollte, was bedeutet die grüne Anzeige eines Lösungswertes bei Dir?

Gruß, kodela

Nachtrag:
Ich muss mich berichtigen, bei den vorstehenden Daten des Profilers fehlen noch 16,8 ms für die Initialisierung des Lösers, also die Zeit, in der die einzelnen Str8ts ermittelt und in einer Liste zusammengefasst wurden. Damit ergeben sich bei einer neuen Messung insgesamt 296 ms, also etwas weniger als eine drittelte Sekunde für das Lösen dieser extrem schweren Str8ts-Aufgabe. Das ist fast der selbe Wert, wie ich oben geschrieben habe. Das kommt daher, dass diesmal der Wert für die Methode loeseAufgabe() um einiges geringer war. Vielleicht kann ich ja die Bilder noch einmal austauschen.

Ja, das ist gelungen!

Und Deine Vorstellungen zur Geschwindigkeit von Java musst Du wohl korrigieren!
Last edited by kodela on Sunday 24. February 2019, 17:24, edited 1 time in total.

Thomas
Posts: 5
Joined: Thursday 21. February 2019, 16:25

Re: Solver für Extreme Str8ts

Post by Thomas » Sunday 24. February 2019, 12:41

Hallo Kodela,
Du hast recht, ich habe bei den Aussagen zur Geschwindigkeit JavaScript gemeint.
Wie war das mit den mehrdeutigen Str8ts? Hast Du da Beispiele?
Gruß Thomas

kodela
Posts: 68
Joined: Thursday 2. July 2015, 23:26

Re: Solver für Extreme Str8ts

Post by kodela » Sunday 24. February 2019, 14:20

Hallo Thomas,

nimm Extreme #033 und entferne in der Zentrumszelle (A5) den Sperrwert 1, nicht die Sperrzelle selbst, dann hast Du zum Beispiel ein Str8ts, welches mindestens zwei Löungen haben kann.

Hast Du meine Frage, was die grüne Anzeige eines Lösungswertes bei Dir bedeutet, überlesen?

Und noch eine andere Frage, in welcher Sprache ist Dein Str8ts-Programm geschrieben?

Gruß, kodela

Thomas
Posts: 5
Joined: Thursday 21. February 2019, 16:25

Re: Solver für Extreme Str8ts

Post by Thomas » Monday 25. February 2019, 10:26

Hallo Kodela,
grünmarkierte Ziffern sind die Lösungen des Backtrackings.
Programmiersprache ist Swift.
Gruß Thomas

kodela
Posts: 68
Joined: Thursday 2. July 2015, 23:26

Re: Solver für Extreme Str8ts

Post by kodela » Wednesday 6. March 2019, 13:17

Hallo Thomas,

eine Frage. Es geht um die Verwendung der "Str8ts"-Bezeichnung. Da hast Du Dich doch mit Jeff Widderich und Andrew Stuart in Verbindung gesetzt. Ich möchte zwar nicht so wie Du in die Öffentlichkeit gehen, lediglich mein Programm auf meiner Homepage interessierten kostenfrei und ohne jede Werbung zur Verfügung stellen. Trotzdem wäre es vielleicht besser, wenn ich wüsste, dass die Rechteinhaber an "Str8ts" nichts dagegen haben. Ja, und da wollte ich Dich fragen, über welche Kontaktadresse Du Dich mit diesen beiden in Verbindung gesetzt hast. Wäre nett, wenn Du mir hier raten könntest, eventuell auch über eine PN.

Gruß, kodela

Post Reply