Solver programmieren

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

Re: Solver programmieren

Post by Robo » Wednesday 17. January 2018, 14:15

Für den Fall, dass jemand hier hereinschaut:
Testet doch mal meinen "Creator" https://is.gd/solverBeta1

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

Re: Creator

Post by hone » Wednesday 17. January 2018, 15:00

Hallo Robo,
Schaut Klasse aus.

Im Creator habe ich mal CanisMajor angesehen. Das Puzzle läßt sich allein mit Standard-Tools lösen. Bei 0:17, bzw. Knoten 106, ist eine Verzweigung drin, wo AC3 als high angenommen wird. Zu diesem Zeitpunkt hätte aber noch die 9 aus CJ8 entfernt werden können, da sie mit A8=89 nicht zusammengeht. Ebenso kann B3 nicht 4 sein. Dann wäre A3=3 und C3=2 und HJ3 inkonsistent. Diese wegfallende 4 führt dann zu einem entscheidenden Spalten-xwing für 4 in CH39

Hab dir vor einigen Tagen eine Mitteilung im Board geschickt. Sieh mal in dein Postfach.

Gruß
hone

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

Re: Solver programmieren

Post by Robo » Thursday 18. January 2018, 11:47

Hallo hone,

vielen Dank für die Mitteilung (die ich jetzt erst gesehen habe) und die Ermutigung.
Ich antworte mal öffentlich, vielleicht kommt ja noch Feedback von anderen.

Bezüglich Veröffentlichung war ich bisher aus mehreren Gründen zurückhaltend.
Zum ersten ist der momentane Stand immer noch nicht gut genug ;-).
Zweitens das Str8ts-Copyright, aber da habt ihr mich ja schon beruhigt.
Drittens bin ich mir nicht sicher, welchen Effekt eine Veröffentlichung (insbesondere des "Creators") auf die Community hat. Zum einen kann dann jeder, der mit dem Extreme nicht zurechtkommt, im Solver mit zwei Klicks die Lösung nachsehen (ist das nicht ein Spaßverderber?), zum anderen gibt es dann möglicherweise noch mehr Gedränge bei den Puzzle-Autoren, weil jeder dieses Tool nutzen kann.

Was meinst du / meint ihr?

Mit dem Großen Hund hast du natürlich recht. Einen Algorithmus für eine weitergehende High-Low-Untersuchung als die bisher eingebaute habe ich schon länger geplant (und ein Design im Kopf), bin aber noch nicht dazu gekommen, da ich mich die letzte Zeit auf andere Funktionalität (wie das 1-Click-Laden der aktuellen Puzzles aus dem Forum) fokussiert habe.

Übrigens: wenn du die Option "brute force line search" einschaltest, findet der Solver die Lösung von Canis Major ohne Verzweigung. Aber das ist natürlich nicht sehr elegant ;-)

Robo

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

Re: Solver programmieren

Post by hone » Thursday 18. January 2018, 14:00

Hallo Robo,
ich finde dein Solver hat einen hohen Reifegrad und kann deshalb problemlos veröffentlicht werden. Du kennzeichnest ihn ja als Beta und somit ist für jeden klar, dass er noch in Arbeit ist. Und, wie schon gesagt, es gibt derzeit nichts Vergleichbares im Web.

Und dass er ein Spassverderber ist, glaube ich auch nicht. Schliesslich kann auch jeder Andrews Solver nutzen, der allerdings weder Wings noch Settis kennt. Ich hätte eher Bedenken, dass versucht wird, dem Solver völlig unentwickelte Muster anzubieten; im Extremfall zB. ein Gitter ohne schwarze Zellen. Deshalb solltest du einige Vorsichtsmassnahmen einführen, wie Timeouts und Limits, zB. für die maximale Zahl gleichzeitiger Nutzer.

So eine Art 1-Click-Laden nutze ich auch. Hole per Drag´n'Drop die URL-Strings aus dem Andrew-Solver für die Weeklies und für die Addons aus dem Daily-Fenster auf die SWING-Oberfläche.

Noch eine Empfehlung: Was im Board als CE bezeichnet wird ist so vielfältig, dass es sich nicht so leicht auf ein Rechnerprogramm umsetzen lässt. Versucht man, alle möglichen Konstellationen von High-Low zu berücksichtigen, so besteht die Gefahr sich zu verzetteln. Der Rechner ist blind und arbeitet deshalb völlig anders als der Mensch. Um das ganze in den Griff zu bekommen nutze ich zwei Methoden, nämlich RangeCombo-Analysen und Sequenz-Checks, um die man als Ultima Ratio irgendwann sowieso nicht herumkommt. Die Entfernung der 4 aus B3 im CanisMajor-Beispiel ist so ein Fall. Man hat dann auch noch den Vorteil auf Multiples usw. verzichten zu können.

Mit einer Art Line-Brute-Force bekomme ich auch alle Weeklies und Addons in einer Sekunde. Für CanisMajor war das nicht nötig, da ich vor Brute-Force auf jeden Fall die Standard-Methoden durchführe.

Auch bei Brute-Force kann es ohne Vorsichtsmassnahmen zu jahrelangen Rechenzeiten kommen.

Kannst du verraten, in welcher Programmiersprache du deinen Solver entwickelst?

Gruß
hone

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

Re: Solver programmieren

Post by Robo » Thursday 18. January 2018, 14:54

Hallo hone,

ok, ich glaube, du hast mich überzeugt. Ich denke, Anfang nächster Woche ist dann ein guter Zeitpunkt.

Ich habe das Ganze in F# und Websharper programmiert, und zwar als reine Client-Anwendung (JavaScript). Was bedeutet, dass ich keine Probleme mit Server-Überlastung etc habe: die Rechenzeit spendiert der User.
(Es macht den Solver allerdings auch ungefähr einen Faktor 10 langsamer als das native F# Programm.)

Kannst du zu RangeCombo und Sequenz-Checks ein paar Worte sagen?
Mein "brute-force-line-search" prüft alle verbleibenden Kombination einer Spalte bzw Zeile auf Gültigkeit.

Gruß

Robo

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

Re: Solver programmieren

Post by Robo » Thursday 18. January 2018, 15:01

Die Zahl in den Knoten ist übrigens die Entropie der verbleibenden Optionen als Zweierlogarithmus.

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

Re: Solver programmieren

Post by hone » Thursday 18. January 2018, 17:17

Hallo robo,

zu den Ranges erst mal eine Glossar:

Sequenz: Ausprägung eines Compartments, zB. 423 für ein dreizelliges Compartment gezählt von links oder von oben
Range: Wertesatz, aufsteigend geordnet, also 234 für obiges Beispiel. Wird repräsentiert durch kleinste Zahl, hier also 2, was
zusammen mit der Compartmentlänge einen eindeutigen Satz beschreibt.

Die Ranges lege ich bei Compartmenterzeugung in Maximalausprägung an, dh. ein 3er-Compartment hat Ranges 1 bis 7, ein 9er nur 1 und einzellige 1-9.

RangeCombos sind Tupel von Ranges der Compartments einer Linie. Im CanisMajor-Beispiel bei 0:17 hat A8 die Ranges 8 und 9, während CJ8 noch 1, 2 und 3 hat. Die Tupel [8,2],[8,3] und [9,3] scheiden aus, weil sich die Ranges überlappen würden. Es bleiben also nur [8,1],[9,1] und [9,2]. Range 3 von CJ8 kommt dabei gar nicht mehr vor, dh. dieser Range wird gelöscht. Als Konsequenz kann dann aus allen Zellen von CJ8 die 9 entfernt werden, da sie nur im Range 3 vorkommt.

Neben dem Überlappungsverbot kommt als weiteres Ausschlußkriterium für die RangeCombos noch hinzu, dass die Tupel sämtliche sicheren Werte der Linie enthalten müssen.

Umgekehrt lassen sich die Combos auch dahingehend auswerten, dass Kandidaten, die in allen Combos enthalten sind, zu sicheren Werten der Linie werden falls sie es nicht bereits sind.

Das war jetzt ein relativ einfaches Beispiel mit zwei Compartments in der Linie, aber es funktioniert genauso mit mehr als 2.
Das ganze benötigt aber etwas Haushaltsführung der Ranges, die einerseits durch eliminierte Zellwerte eingeschränkt werden können aber auch extern durch Combo-Analysen.

Im zweiten Fall des Beispiels (Entfernung der 4 aus B3) reichen RangeCombos nicht aus, sind aber notwendig. Sie reduzieren die mögliche Ranges von AC3 auf 1,3 und 4. Hier hilft nur ein Sequenz-Check, dh. man prüft bei jedem Kandidaten, ob mindestens eine Sequenz existiert. Für B3=4 gäbe es nur 243, was aber den verbotenen Range 2 hat.

Dieser Sequenz-Check ist weniger aufwendig als vielleicht angenommen und er erschlägt nebenbei sämtliche Standardmethoden wie naked und hidden multiples, no neighbour, large gap usw. Diese Standardmethoden sind ohnehin nicht ausreichend. Man müsste sie erweitern auf stranded Teilsequenzen und das auch noch für internal compartments. Und dann kann man immer noch nicht sicher sein, ob alles berücksichtigt wurde.

Gibt auch noch spezielle Fälle, wo ein Range die Combos überlebt, aber keine Sequenz zum Range existiert.

Soll aber jetzt mal ausreichen, war das wesentliche zu RangeCombos und Sequenz-Checks.

Gruß
hone

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

Re: Solver programmieren

Post by Robo » Thursday 18. January 2018, 17:53

Mit Ranges und Tuples von Ranges arbeite ich auch, aber ich glaube, du machst das deutlich effizienter. Darüber muss ich nochmal nachdenken.
Erstmal vielen Dank für die ausführliche Hilfe!
Robo

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

Re: Solver programmieren

Post by Klaus » Thursday 18. January 2018, 20:34

Hallo Robo,

also ich muss sagen, dass ich mit deinem Link nicht zurechtkomme. Ich weiß nicht was ich tun soll um zu steuern was ich tun will.

Ist das ein Solver, ein Creator, oder beides? Aktuell ist es so, dass, sobald ich den Link aufrufe, sofort irgendeine Berechnung los läuft, ich denke er versucht ein völlig leeres Board zu lösen (wahrscheinlich ein Überbleibsel von meinem letzten Besuch!?). Ich weiß aber auch nicht durch was ich das angetriggert habe oder wie ich es stoppen könnte. Oder wie ich überhaupt irgendwas anstarte oder beende?

Kein Plan meinerseits.

Ratlose Grüße,
Klaus

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

Re: Solver programmieren

Post by hone » Thursday 18. January 2018, 22:24

Hallo Klaus,
robos Creator ist Editor und Solver zugleich. Das letzte gewählte Puzzle läuft am Anfang los. Andere kannst du mit LOAD oder RETRIEVE laden. Wenn unter SETTINGS "Editor Only" angekreuzt ist, kannst du auch editieren, sowohl geladene als auch neue. Etwa geladene laufen dann auch nicht los, erst bei Abschalten des Edit-Modes.

Ich finde es beeindruckend wie er die zero hints ohne Vorgaben schafft.

Gruß
hone

Post Reply