Solver programmieren

Robo
Posts: 22
Joined: Monday 1. January 2018, 11:47

Solver programmieren

Post by Robo » Monday 1. January 2018, 15:19

Hallo allerseits,
ich bin gerade erst auf dieses Forum gestoßen, obwohl ich seit Jahren str8ts.com verfolge.
Ist das hier ein guter Platz zum Austausch über Str8ts-Solver-Programme?
Zur Diskussion über Algorithmen, Programmiersprachen, etc. (Oder auch nur, um Anerkennung von anderen Experten zu bekommen ;-)).
(Lieber noch in Englisch, aber im englischsprachigen Forum ist ja noch weniger los ;-))
Robo

Klaus
Posts: 27
Joined: Friday 15. January 2016, 11:57

Re: Solver programmieren

Post by Klaus » Saturday 6. January 2018, 10:13

Hallo Robo,

ich nehme an, dass das hier kein besonders guter Platz für Diskussionen ist. Offensichtlich wenig Leute hier und noch weniger die schreiben.

Aber man kanns ja mal probieren. Also schreib einfach, damit ich dir die gewünschte Anerkennung zollen kann (so du mich denn als Experten gewillt bist zu akzeptieren).

Schöne Grüße an alle,
Klaus

Robo
Posts: 22
Joined: Monday 1. January 2018, 11:47

Re: Solver programmieren

Post by Robo » Sunday 7. January 2018, 17:01

Hallo Klaus,

Feedback vom Urvater der Extra-Str8ts wäre natürlich der Gipfel der Anerkennung!

Ich hätte aber erst mal folgende Frage:
Ich löse die Weekly Extremes seit Jahren und möchte auf keinen Fall etwas tun, was str8ts.com abträglich wäre, oder gar mit Andrew oder anderen Probleme bekommen.
Den Solver habe ich vor allem aus Spaß am Programmieren gebaut, und zum Lernen einer neuen Sprache.
Kann ich den Source Code auf github stellen, oder würde das zu Problemen bzgl str8ts-Copyright führen?

Hier übrigens eine read-only-Version des Solvers für die letzten beiden Extremes:
is.gd/solution_W393
is.gd/solution_W394

Viele Grüße

Robo

hone
Posts: 59
Joined: Sunday 7. February 2016, 13:30

Re: Solver programmieren

Post by hone » Sunday 7. January 2018, 20:23

Hallo Robo,

zunächst mal finde ich deinen Solver mit den Darstellungen der BackTracks und Begründungen für die Schritte Klasse.

Selbst habe ich vor etwa 2 Jahren damit angefangen (Java/Swing) und am Anfang die Anzahl der Leute mit Solvern maßlos überschätzt. Es sind vielleicht zwei handvoll. Trotzdem ist das hier der richtige Platz, denn das Board ist flüchtig. Du kannst auch in Englisch posten, dann erreichst du mehr Leute; im Extremes Forum sind etliche gemischtsprachige Einträge.

Dass es zu Problemen mit dem CopyRight kommt glaube ich nicht. Wie gesagt, es sind nur wenige, die über einen Solver verfügen und solange du damit kein Geld machst oder Str8ts als deine Erfindung ausgibst (gab es schon) wird dir niemand Ärger bereiten. Auf github gibt es auch einige nicht weiterverfolgte Solver.

Eine Anregung zur Oberfläche: Für mich ist die Darstellung des Gitters in Firefox etwas zu klein; insbesondere wenn man noch zusätzlich die Ansicht verkleinern muß um die gesamte Schrittleiste auf dem Schirm zu haben.

Ansonsten wünsche ich dir viel Spaß und Erfolg beim weiteren Ausbau deines Solvers.

Viele Grüße
hone

Klaus
Posts: 27
Joined: Friday 15. January 2016, 11:57

Re: Solver programmieren

Post by Klaus » Sunday 7. January 2018, 22:03

Hallo Robo,

ich kann mich hone nur voll umfänglich anschließen. Diese Art der Präsentation des Lösungswegs ist wirklich klasse, vollste Anerkennung. Vor allem das völlig wahlfrei hin und her wechseln zwischen den einzelnen Punkten des Lösungswegs ist sehr hilfreich.

Kleine Anmerkungen:

Eine größere Darstellung des Boards wäre sicherlich gut. Etwas umfangreicher im linken Teil, dafür der Lösungsweg, ggf. mit Zeilenumbruch, im rechten Teil wäre vielleicht etwas übersichtlicher.

Zu den Abkürzungen, ich weiß nicht was HL oder BF meint.

Inhaltlich hab ich natürlich nicht alles geprüft, aber noch ganz konkret zu 394: Was ab Punkt 105 in Reihe H mit 89 passiert, kommt mir ein bisschen komisch vor. Ein offensichtliches "naked pair" das 5,6 Schritte lang unberücksichtigt bleibt, sogar noch HL(?), UR und Setti dazwischen, ich weiß nich...

Spannend find ich, welche Wege nach welchen Kriterien der Solver einschlägt. Welche Chains, wie lange, wie viele, etc.? Hast du ihn schon mal auf die ganz harten Nummern losgelassen, z.B. hone's Christmas Puzzle 2016 FreeB1?

Zum Copyright weiß ich nix, ich denke auch, solange du keine kommerziellen Interessen hast... Schreib doch einfach mal an Andrew (hab nicht den Eindruck als wär er noch besonders an Str8ts interessiert).

Ride on,
Klaus

FPSt
Posts: 16
Joined: Friday 2. December 2011, 22:26

Re: Solver programmieren

Post by FPSt » Monday 8. January 2018, 09:22

Hallo Robo
Das ist ein interessanter Solver. Du hast einen ähnlichen Ansatz der Visualisierung realisiert, wie er auch in meinem Programm enthalten ist. Die Visualisierung ist bei Deiner Lösung spezifisch für einen zu streichenden Kandidaten. Mein Programm zeigt die verwendeten Regeln und die davon betroffenen Kandidaten an:
ToolTip.png
ToolTip.png (10.95 KiB) Viewed 18703 times
Hier die vier Regeln die in G1 zum Ergebnis kommen, dass 7 und 9 gestrichen werden. Die Kürzel RSC, RSE und RH4 sind nicht so selbsterklärend, wie die Texte in Deinem Solver. Hier muss ich noch nachbessern. RH4 ist die "Hidden 4th"-Regel. Die damit gefundenen Kandidaten sind ebenfalls angegeben. (Ref:_2345____ )
Bei einfachen Rätseln ist es oft zu beobachten, dass zu streichende Kandidaten von mehreren Regeln gefunden werden. Bei den Extremen von Andrews ist das weniger der Fall. Das wäre auch ein wichtiger Punkt im Zusammenhang mit der Bewertung eines Rätsels.
Mein Programm kann die Extremen noch nicht so gut lösen. Einfach deshalb, weil einige der bekannten Regeln noch nicht enthalten sind.
Deine Visualisierung aller Stufen der Lösung ist eine gute Anregung. Mein Programm kann bisher nur durch Interaktion Lösen und speichert die Zustände nicht. Aber es werden alle Zustände als Bild und Text-Protokoll gespeichert. Darin sind die Texte wie im Bild zu sehen für alle Felder enthalten.

FPSt

Robo
Posts: 22
Joined: Monday 1. January 2018, 11:47

Re: Solver programmieren

Post by Robo » Monday 8. January 2018, 13:41

Hallo hone, Klaus und FPSt,
vielen Dank für eure Antworten, Kommentare, Fragen und Anregungen!
Ich bin gerade in Eile und werde daher auf einige Fragen separat zurückkommen.
Aber als Beispiel für eine "harte Nuss" hier morl's 1-hint-Variante von gestern:
https://is.gd/morl1hint
Robo
Last edited by Robo on Tuesday 9. January 2018, 09:27, edited 1 time in total.

Robo
Posts: 22
Joined: Monday 1. January 2018, 11:47

Re: Solver programmieren

Post by Robo » Monday 8. January 2018, 19:25

@FPSt: Ja, das sieht in der Tat sehr ähnlich aus. Mit tooltips / popups zu arbeiten, ist bei den vielen Informationen auch fast die einzige Möglichkeit, diese "verdaubar" anzubieten. Schön, das bei dir auch zu sehen!
Auch mein Solver ist bei Weitem noch nicht vollständig. Dabei finde ich es immer wieder faszinierend, zu sehen, wie gut unser Gehirn in der komplexen Musterverarbeitung ist. Ein naked pair zum Beispiel fällt uns gleich ins Auge, während das als Algorithmus korrekt zu fassen nicht ganz simpel ist.
Das führt mich auch zu der Frage von Klaus: zur Rechenzeitoptimierung ich habe die Algorithmen in Gruppen geordnet und wende die Gruppen (geordnet von einfach bis aufwendig) der Reihe nach an, bis ich Treffer habe. Dann fange ich wieder von vorne an. UR, BCA und X-Wing sind schneller als die Tuples und werden daher zuerst abgearbeitet.
Mit der Anordnung kann man Zeit- und Raumoptimierung gegeneinander abtauschen, ich habe versucht, einen guten Mittelweg zu finden. Bei den Chains versuche ich es zuerst mit offenen High-Low-Entscheidungen. Wenn es keine gibt, dann mit den Zellen mit den wenigsten Optionen, von denen ich einfach die erste nehme.
Irgendwann will ich auch noch eine Optimierungsschleife über das ganze legen, die mir den Lösungsbaum mit den kürzesten Chains gibt.
Ja, und die Anordnung auf dem Bildschirm muss ich auch irgendwann überarbeiten. Vielleicht ein separates Window für das Board...
Leider wird demnächst meine Zeit wieder enger. Die letzten Wochen konnte ich (mit Freude) viel programmieren. Ich will sehen, dass ich den Creator noch auf einen guten Stand bringe und dann auf github stelle.
Soviel für heute.
Robo
Last edited by Robo on Tuesday 9. January 2018, 09:27, edited 1 time in total.

hone
Posts: 59
Joined: Sunday 7. February 2016, 13:30

Vergleich Absprungstelle 2:16 von morl1hint

Post by hone » Monday 8. January 2018, 22:01

Hallo Robo,
habe mal einen Vergleichslauf bis zu deinem Knoten 2:16 in morl1hint mit meinem Solver gemacht:
2:16 Vergleich
2:16 Vergleich
morl1hint_c216.png (8.95 KiB) Viewed 18679 times
Da hat dein Solver also noch etwas Luft nach oben, damit er nicht zu früh ins Chaining geht.
Benutzt worden sind nur intra-line Methoden, was man im Board-Jargon auch CE (Careful Elimination) nennt.
Nehmen wir als Beispiel C2, wo dein Solver noch die 5 hat. Die würde aber zu C47 high führen und für C9 ist dann kein Wert mehr übrig.

Sehe ich das richtig, dass dein Solver nach einer gefundenen Lösung auch alle anderen bisher ausgelassenen Verzweigungen durchläuft um andere Lösungen zu suchen bzw. die Eindeutigkeit zu verfizieren?

Viele Grüße
hone

Robo
Posts: 22
Joined: Monday 1. January 2018, 11:47

Re: Solver programmieren

Post by Robo » Monday 8. January 2018, 22:42

Hallo hone,
ja, mein Solver hat mit Sicherheit noch viel Luft nach oben. Eine ganze Reihe Algorithmen stehen noch auf meiner todo-Liste.
Und, ja, wenn ich die Option "Assume Uniqueness" ausschalte, findet der Solver alle Lösungen.
Robo

Post Reply