Solver programmieren

Klaus
Beiträge: 21
Registriert: Freitag 15. Januar 2016, 11:57

Re: Solver programmieren

Beitrag von Klaus » Donnerstag 18. Januar 2018, 23:10

Hallo hone,

ich bezweifle nicht, das man die Seite irgendwie bedienen kann, aber es erschließt sich mir nicht wie. Was hat "Editor only" mit irgendeinem Berechnungsversuch zu tun? Warum läuft ständig irgendwas los ohne das ich das will?

Dass es zero hints ohne Vorgaben schafft, mag beeindruckend sein, aber es sagt mir nichts. Ein Haufen Branches, von denen einige schließlich irgendwie, irgendwann durchkommen. Was mich interessiert ist das Maximum an Eliminierung, das allein Struktur hergibt. Also in diesem Fall 2 Kandidaten in jeder Zelle und die Fünfer gelöst, das ist die Natur dieser Struktur, die möcht ich sehn, das ist faszinierend. Im Dschungel von Verzweigungen kann ich nix erkennen.

Robo, ich hoffe ich war jetzt nicht zu negativ, deine Ideen sind wirklich klasse, die Darstellung beeindruckend.

Str8ts on,
Klaus

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Solver programmieren

Beitrag von Robo » Freitag 19. Januar 2018, 10:34

Hallo Klaus,

danke für das Feedback!

Tut mir leid, dass da etwas nicht funktioniert und meine Dokumentation so spärlich ist.
Vielleicht kannst du erst mal mit Ctrl F5 sicherstellen, dass du die neueste Version hast.
Zweitens unter Settings "Editor only" einschalten.
Dann, wie von hone beschrieben, ein Puzzle laden, oder eins erstellen (das wird oben rechts beim Fragezeichen kurz erklärt).
Dann "Editor only" wieder ausschalten.

"Editor only" ausgeschaltet bedeutet hier "autosolve" eingeschaltet. Jede Änderung im Input (editieren oder neu laden) triggered dann den Solver. Ich finde das praktisch. Ich sehe aber, dass die Option in dieser Form verwirrend ist. In der Tat hieß diese bis vor Kurzem noch "autoSolve". Es gab aber Gründe, die Logik umzudrehen (damit beim allerersten Aufruf der Solver sichtbar ist). Ich denke, ich werde zu dem Setting "autoSolve" zurückkehren und gleichzeitig einen Button "Solve" irgendwohin setzen. Das ist dann hoffentlich weniger verwirrend.

Der Kern-Solver ist noch nicht besonders gut, daher gibt es bei vielen Puzzles mehr Verzweigungen als nötig. Da das ganze aber für mich als Programmierübung zum Erlernen von F# und Websharper angefangen hat, habe ich zunächst mal Funktionen hinzugefügt, die ich für die Benutzung für nützlich hielt.

Viele Grüße

Robo

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Solver programmieren

Beitrag von Robo » Samstag 20. Januar 2018, 09:28

@Klaus: Du kannst im Menu unter "Retrieve" jetzt auch hone's 2016 xmax B1 finden :-)

Klaus
Beiträge: 21
Registriert: Freitag 15. Januar 2016, 11:57

Re: Solver programmieren

Beitrag von Klaus » Samstag 20. Januar 2018, 10:08

Hallo Robo,

nochmals, ich hab das nicht als Kritik gemeint.
Ich bin ein old-fashioned-guy. Bei einem Tool möchte ich klare Steuerelemente um dem Tool zu sagen was es wann tun soll. Hyperaktive Oberflächen sind nich so mein Ding. Aber das ist nur mein Geschmack, und man kann das selbstverständlich auch anders sehen und andere Schwerpunkte haben,

Egal wie spielstark dein Solver auch ist, früher oder später kommst du an den Punkt, an dem du Annahmen, und ggf. auch deren Gegenteil, untersuchen musst. Und hier gibt es interessante Fragen und Ansätze:

- Welche Annahmen führen zu Widersprüchen (mit oder ohne weitere Unterannahmen)
- Welche Annahmen führen zu einer Lösung (mit oder ohne weitere Unterannahmen)
- Wie lange sind die Wege bis zu deren Ergebnis
- Wie schwierig (von einem menschlichen Standpunkt aus) sind die Wege bis zu deren Ergebnis
- Was kann in Summe alles eliminiert werden und was verbleibt
- etc.

Das sind alles Fragen, die ich einem Solver stellen will, und die er mir optimalerweise in verständlicher Form beantworten soll. Dann hab ich das Gefühl, ich "verstehe" das Rätsel, ich sehe Schwachpunkte, die "wahre" Natur. Klingt schön hochtrabend, nich?
Das dabei, sozusagen nebenbei, auch die Lösung(en) abfällt, ist nett.

Ich denke deine Schwerpunkte waren jetzt erstmals anders und das ist dir sehr gut gelungen.

Peace and Love,
Klaus

Klaus
Beiträge: 21
Registriert: Freitag 15. Januar 2016, 11:57

Re: Solver programmieren

Beitrag von Klaus » Samstag 20. Januar 2018, 10:30

Hi Robo,

ja, geniales Ding vom Entdecker der KnightJumps. Sehr interessant zu untersuchen, vor allem auch ohne die 8 als Vorgabe, zähes Luder.

Schönes Wochenende,
Klaus

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Solver programmieren

Beitrag von Robo » Samstag 20. Januar 2018, 12:03

In der Tat zäh. Aber trotzdem findet der Solver alle 86 (oder so) Lösungen.
(Ja, ich weiß ;-), deren gemeinsame Struktur zeigt er (noch) nicht).
Schönes Wochenende!
Robo

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Solver programmieren

Beitrag von Robo » Samstag 20. Januar 2018, 12:15

Nochmal zur Wahren Natur:
- Welche Annahmen führen zu Widersprüchen (mit oder ohne weitere Unterannahmen)
- Welche Annahmen führen zu einer Lösung (mit oder ohne weitere Unterannahmen)
- Wie lange sind die Wege bis zu deren Ergebnis
- Wie schwierig (von einem menschlichen Standpunkt aus) sind die Wege bis zu deren Ergebnis
- Was kann in Summe alles eliminiert werden und was verbleibt
- etc.
Ich weiß nicht, ob das klar geworden ist: du kannst im linken Brett Ziffern eintragen oder löschen oder umfärben und siehst in Sekunden die neue Lösung (oder dass es keine Lösung gibt oder dass es mehrere gibt).
Der Lösungsbaum zeigt durchaus den Schwierigkeitsgrad. Verzweigungen sind Chains, kurze Verzweigungen sind head chains. Farbige Knoten sind non-CE. Das alles ist natürlich kein klares Maß für den gefühlten menschlichen Schwierigkeitsgrad, gibt aber doch gute Hinweise.

hone
Beiträge: 32
Registriert: Sonntag 7. Februar 2016, 13:30

Re: Solver programmieren

Beitrag von hone » Samstag 20. Januar 2018, 14:04

Hallo robo,
das mit den 86 Lösungen stimmt schon mal. Scheint mir, dein Solver benötigt härtere Sachen ;)
Das folgende Puzzle nehme ich selbst als Benchmark für Geschwindigkeitstests, komme damit so auf 4 bis 5 Minuten (bei einem Mehr-Core-System kommt jedesmal was anderes heraus).
Inner10_1W.png
Inner10_1W
Inner10_1W.png (3.71 KiB) 735 mal betrachtet
Ohne den Clue sind es 9400 Lösungen. Man kann sich aber die Arbeit bei leeren Mustern sehr erleichtern, indem man ein passendes Compartment auf Low setzt und am Schluß die Lösungen durch Flippen verdoppelt. Reduziert die Komplexität massiv.

Gruß
hone

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Solver programmieren

Beitrag von Robo » Samstag 20. Januar 2018, 15:47

Hallo hone,

beziehen sich die Rechenzeiten auf die 1-Clue- oder die 0-Clue-Version?

Mein Web-Solver (den Link hast du ja) braucht für die 1-Clue-Version auf meinem Laptop dreieinhalb Sekunden für die Algorithmen. Mit dem ganzen UI dauert es ca 15 Sekunden bis der ganze Lösungsbaum aufgebaut ist.
Die Windows-Version (ohne UI und nativer Code (kein Javascript)) braucht ca 1 Sekunde.

Ohne den Clue komme ich auf 1716 Lösungen, die die Windows-Version in ca 3 Minuten ausspuckt.

Das Auf-Low-Setzen eines Compartments macht der Solver automatisch bei der ersten Verzweigung, berechnet dann aber auch noch die High-Version. Das kann man ganz schön bei den morl-Zero-Clues dieser Woche beobachten. Da könnte man natürlich einen Faktor zwei einsparen für Zero-Clue-Puzzles.

Gruß
Robo

hone
Beiträge: 32
Registriert: Sonntag 7. Februar 2016, 13:30

Re: Solver programmieren

Beitrag von hone » Samstag 20. Januar 2018, 16:44

Hallo robo,
die Zeiten bezogen sich auf den einen Clue.
Ich nutze Backtracking eigentlich nur fürs Generieren (Zellwerte oder Ranges), ansonsten suche ich die Lösungen mit Nachbarschaftsuntersuchungen.
Habe jetzt spaßhalber mal die 1 Clue-Version im RangeMode "Generieren" lassen und nach einigen Sekunden war das Ergebnis tatsächlich da. Dabei wurden nur 3 Ranges gesetzt (nach einigen Sackgassen und Rücknahmen):
Clue 1 : C8..C9 auf 8
Clue 2 : A6..D6 auf 5
Clue 3 : D5..D9 auf 1

Der erste ist sogar überflüssig, dh. es reichen die zwei letzten.
Offenbar hast du eine Methode gefunden, mit der du gezielt die geeignetsten Compartments und Ranges findest.

Ohne Clue sind es tatsächlich 9400 Lösungen. Im nächsten Bild sind die 4700 Lösungen für G3low übereinandergelegt.
Inner10_G3low.png
Inner10_G3low.png (9.29 KiB) 733 mal betrachtet
Ein sinnvolles Komplexitätsmaß suche ich auch schon lange. Da hast du scheinbar mit deiner Entropie auch eines gefunden.

Gruß
hone

Antworten