IngoAlthoefer
20.06.2016, 16:35

+19Puzzle mit 4x4 Teilen

Hallo,

aus den 1950er Jahren stammt ein Puzzle, wo 4 x 4 Teile
so aneinander zu legen sind, dass alle Übergänge passen.
Der Schöpfer (Hans Bouwmeester aus den Niederlanden?!)
beschrieb es mit 16 Pappkärtchen, wo auf jedem ein bestimmtes
Muster aus vier Nullen/Einsen abgebildet war. Jede der
2 hoch 4 Möglichkeiten kam genau einmal vor.

Schon vor einiger Zeit habe ich dieses Puzzle mit LEGO-Steinen
realisiert:

[image]


Die 16 Teile in zufälliger Anordnung. 0 und 1 sind durch die Farben rot und blau ersetzt.



[image]


Meine einfache Konstruktion mit schwarzen Steinen als Unterschicht.



[image]


Links eine Teillösung aus sieben Elementen. Am Ende müssen an allen Übergangsstellen
alle Farben zueinander passen.

Viel Spaß beim Nachbauen und Probieren. Es gibt mehr als 400 Lösungen.

Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


Mitglieder, denen dieses MOC gefällt:

doktorjoerg , Custer , Cran , Seeteddy , Legomichel , Dirk1313 , renrew , Legobecker , Plastik , MARPSCH , fannie1981 , Lukutus , cimddwc , doe , uefchen , Titus , naseneis , nvneuss , JuL (19 Mitglieder)

52 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

cimddwc
06.07.2016, 10:50

Als Antwort auf den Beitrag von drdwo

Re: 255er Lösung für 4 Farben

drdwo hat geschrieben:

Wieviele Versuche waren es bis zum 253er? Wenn es weniger als 2.36e11 Versuche waren, war es entweder Glück oder ich sollte noch etwas an meinem Verfahren feilen.

1.76e12. Wenn auch - siehe früheres Posting - einige zu viel gezählt worden sein dürften.

Grüße,
Andreas



Eisbär
06.07.2016, 11:58

Als Antwort auf den Beitrag von IngoAlthoefer

Farbfrage

Liebär Ingo!

Mondrian ist gut, aber war der damals auch in Billund schon weltbärühmt?

Es gab mal die Frage, von Lego in einem Preisausschreiben gestellt, welches die ersten (Anzahl vergessen: drei, vier?*) Legofarben waren.

Rot und weiß, und wer dabei an Pommes denkt, irrt, aber welche noch? 10x20 Grundplatten waren ja grau.

Es gibt Schlitzsteine auch in blau und gelb.

Schwarz war auch schon früh vertreten.

Man sortiert seine LEgos ja nicht nach Farben, sondern nach Steinesorten. Da ich aber die Macke (Stimmen aus dem OFF: Wenn's nur die wäre!) habe, vergilbte Legos zu bearbeiten, sortiere ich weiße raus, dann auch blaue und graue. Und was bleibt nach? Richtig. Die belgischen. (Seltene farben hab' ich allErdings extra.) Siehste, und weil ich von den Farben soviele habe, nehme ich sie als Unterbau und Stütze und Füllsel.

Mondrian ist zwar gut, aber in Lego allzuleicht nachzubauen. Ich hatte mich.a mal an suprematistischen und kubistischen Sachen, und nicht nur dem schwarzen Quadrate, versucht, sind aber offline.

*Früher, aber nicht so früh wie die Frage es meint, gab's ja sone Art Logo

[image]

in den Legogrundfarbe, aber die Anzahl stimmte mit der in der Frage nicht übärein. Gelbrotblauweißschwarz. Daher habe ich keine Antwort.

Avantgarde-Grüße
M.a



IngoAlthoefer
06.07.2016, 12:07

Als Antwort auf den Beitrag von drdwo

Re: 255er Lösung für 4 Farben

Hallo Dietmar,

drdwo hat geschrieben:

Hier etwas Statistik über die letzten 22 Stunden:

Geschätzt 7.5e13 Versuche ( 22h * 3600s * 9.5e8)
318 mal >= 253 - 2.36e11 Versuche pro 253er
29 mal >= 254 - 2.59e12 Versuche pro 254er
3 mal >= 255 - 2.5e13 Versuche pro 255er

Ich extrapoliere mal: jedes Mal, wenn der Wert um 1 ansteigt,
geht die Anzahl gefundener um den Faktor 10 runter: 300 -> 30 -> 3
Also solltest Du bisher 0,3 256er gefunden haben (Hinweis für mich.a:
das ist angewandte diskrete Optimierung; nix mit ausgebrannten Halbbussen :-).
Also sollten ungefähr alle 3 Tage ein 256er dabei sein, wenn
das mit dem Faktor 10 allgemein gilt. (Aber jetzt bitte nicht spekulieren, ob
sich alle 30 Tage ein 257er findet ...)

Komisch ist, das die drei 255er alle auf einem (von 5) Rechnern
gefunden wurden. Die Wahrscheinlichkeit dafür ist glaube ich relativ gering.

Ist aber noch nicht statistisch signifikant. Der erste Treffer ist zufällig
auf diesem Rechner. Dann ist die W-keit für die beiden folgenden 1/25 = 4 %.

Deshalb vermutete ich zunächst, das ich auf diesem Rechner versehentlich
irgendetwas anders gemacht habe - habe aber nichts gefunden.

Vielleicht kannst Du ja "trotzdem" probehalber den Code dieses Rechners
auf einen der vier anderen übertragen. Oder hat der Rechner vielleicht
ein anderes Verfahren, den Pseudozufall zu initialisieren?

Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


Eisbär
06.07.2016, 12:47

Als Antwort auf den Beitrag von IngoAlthoefer

Re: 255er Lösung für 4 Farben

Liebär Ingo!

Also solltest Du bisher 0,3 256er gefunden haben (Hinweis für mich.a:
das ist angewandte diskrete Optimierung; nix mit ausgebrannten Halbbussen :-).


Eher dreiviertel, denn 0,3 von 256 sind: dreimal 250 = 750 plus dreimal 6 = 18 macht 768 durch zehn macht 76,8. FehlerABSchätzung: 70 mal drei sind 210, 80 mal drei sind 320, liegt so passend dazwischen, zufrieden.

Wo aber bleibt der Omnibus?

Und was ist unanwendbäre indiskrete Malifizierung?

Stimme aus dem OFF: Das is, wenn's kaputt is und in's Auge fällt.



Aufdringliche Grüße
M.a



IngoAlthoefer
06.07.2016, 12:51

Als Antwort auf den Beitrag von Eisbär

LEGondrian

Lieber mich.a,

Eisbär hat geschrieben:

Mondrian ist gut, aber war der damals
auch in Billund schon weltbärühmt?

Die hatten zwar nur einen Bahnhof und drei Strassen,
aber Mondrian (gestorben 1944) kannte und schätzte
man überall. Warum ich das "1944" so gut weiss? Urheberrecht
schützt ja für 70 Jahre nach dem Tod des Künstlers.
Und 70 Jahre plus 1 Tag nach Mondrians Tod eröffnete in
Hamburg eine grosse Mondrian-Ausstellung. (So etwas passiert
halt, wenn ein Kunstbetrieb mit wenig Geld auskommen muss.)

Es gab mal die Frage, von Lego in einem Preisausschreiben gestellt,
welches die ersten (Anzahl vergessen: drei, vier?*) Legofarben waren.

Ich glaube, es waren (in CA) weiss, rot und blau.
Gelb kam etwas später.

Wenn ich mich recht entsinne, kamen Schwarz und transparent erst,
als es ABS war.

Man sortiert seine LEgos ja nicht nach Farben, ...

Doch! Es gab z.B. 1965 einen Basiskasten mit roten und weissen,
einen anderen mit gelben und blauen. So wussten wir Geschwister
immer, wem was gehörte.

[image]


Avantgarde-Grüße zurück,
Ingo (war schon im schwedischen Kulturfernsehen, 6 Minuten mit LEGO-Kunst).


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


IngoAlthoefer
06.07.2016, 12:53

Als Antwort auf den Beitrag von Eisbär

Re: 255er Lösung für 4 Farben

LIeber Mich.a,

bitte vorsichtig sein, sonst verschreckst Du noch den Dietmar.
Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


drdwo
06.07.2016, 16:12

Als Antwort auf den Beitrag von cimddwc

Editiert von
drdwo
06.07.2016, 16:19

Re: 255er Lösung für 4 Farben

1.76e12

ist ca. Faktor 7.5 zu meiner Knotenzahl. Leider ist eine Stichprobe mit nur einem Element statistisch "etwas unsicher", es wäre jedenfalls ein Hinweis, das sich meine Verbesserungen der Suche beim 4-er stärker auswirken als beim 3-er (ca. Faktor 2).



drdwo
06.07.2016, 16:17

Als Antwort auf den Beitrag von IngoAlthoefer

Re: 255er Lösung für 4 Farben

Vielleicht kannst Du ja "trotzdem" probehalber den Code dieses Rechners
auf einen der vier anderen übertragen. Oder hat der Rechner vielleicht
ein anderes Verfahren, den Pseudozufall zu initialisieren?

Der Code war identisch wenn ich nichts übersehen habe. Bez. des Faktors 10 für 255/256 bin ich etwas skeptisch,
evtl. ist der Faktor größer. Bin auch unsicher ob man 80/81 er Verhältnisse beim 3-er auf das 4-er übertragen kann.



drdwo
07.07.2016, 07:52

Als Antwort auf den Beitrag von IngoAlthoefer

potentielle Lösung des 4-Farben Problems zur Verifikation

Hier ist der 2. Versuch einer (potentiellen) Lösung des 4-Farben Lego-Puzzles zur Verifikation:

00 01 10 00 01 11 10 02 20 03 32 23 33 31 13 30
11 10 00 01 12 21 12 22 21 11 13 31 11 12 20 02

11 10 00 01 12 21 12 22 21 11 13 31 11 12 20 02
11 11 10 01 11 11 12 20 01 13 32 22 23 32 23 33

11 11 10 01 11 11 12 20 01 13 32 22 23 32 23 33
10 00 01 11 12 20 00 02 21 11 11 13 30 02 23 31

10 00 01 11 12 20 00 02 21 11 11 13 30 02 23 31
10 00 00 01 10 01 12 21 10 03 33 30 03 30 01 10

10 00 00 01 10 01 12 21 10 03 33 30 03 30 01 10
22 20 02 20 02 22 20 02 21 12 22 23 32 21 13 31

22 20 02 20 02 22 20 02 21 12 22 23 32 21 13 31
11 12 20 00 00 02 20 01 12 23 32 20 03 33 33 31

11 12 20 00 00 02 20 01 12 23 32 20 03 33 33 31
02 22 22 22 21 11 10 02 21 12 20 03 30 03 33 33

02 22 22 22 21 11 10 02 21 12 20 03 30 03 33 33
12 21 12 22 22 22 20 02 21 13 32 21 12 22 20 01

12 21 12 22 22 22 20 02 21 13 32 21 12 22 20 01
02 20 01 10 00 01 11 10 00 01 12 23 33 31 13 32

02 20 01 10 00 01 11 10 00 01 12 23 33 31 13 32
23 33 30 03 30 03 31 13 32 23 30 02 21 11 13 31

23 33 30 03 30 03 31 13 32 23 30 02 21 11 13 31
33 32 20 03 33 33 32 22 22 21 13 31 13 30 02 21

33 32 20 03 33 33 32 22 22 21 13 31 13 30 02 21
12 23 31 10 02 23 32 23 33 31 12 20 03 30 03 30

12 23 31 10 02 23 32 23 33 31 12 20 03 30 03 30
31 10 03 33 32 22 21 13 30 00 03 30 02 22 23 31

31 10 03 33 32 22 21 13 30 00 03 30 02 22 23 31
13 30 00 00 00 03 32 23 32 23 31 11 13 30 00 01

13 30 00 00 00 03 32 23 32 23 31 11 13 30 00 01
10 01 13 33 31 13 30 03 33 32 23 32 21 10 03 31

10 01 13 33 31 13 30 03 33 32 23 32 21 10 03 31
23 33 31 13 30 00 00 01 10 01 11 10 03 32 20 02

Gestern früh hatte ich mein Programm zunächst verschlimmbessert, ich fand kaum noch 254er. Nachdem ich den Fehler behoben und meine letzte Verbesserung (Optimierung des Abbruchkriteriums) implementiert hatte, startete ich gestern Abend einen neuen Versuch.

Meine Rechner liefen heute Nacht mit der neuen Version des Programms ca. 11h, drei 6-core, und zwei 4-core Machinen, jeweils ca. 4.2Ghz. Hier ist für alle Rechner die Häufigkeit, mit der eine Suchtiefe [247-256] erreicht wurde:

6a [35026, 30213, 25359, 21334, 21218, 20576, 19732, 17894, 16153, 12764, 8542, 4760, 2760, 1206, 673, 233, 69, 18, 4, 0]
6b [31076, 26893, 22536, 18937, 18828, 18230, 17484, 15808, 14239, 11340, 7634, 4164, 2434, 1081, 618, 216, 71, 15, 4, 0]
6c [36143, 31159, 26185, 21982, 21831, 21168, 20351, 18415, 16657, 13353, 9013, 4919, 2871, 1226, 693, 249, 79, 16, 1, 0]
4a [25818, 22250, 18676, 15700, 15604, 15121, 14518, 13144, 11855, 9471, 6357, 3464, 2004, 857, 457, 154, 60, 11, 2, 1]
4b [26442, 22815, 19241, 16124, 16011, 15479, 14836, 13392, 12068, 9609, 6461, 3541, 2095, 860, 447, 141, 43, 7, 1, 0]

Wir haben also insgesamt 1 256er, 12 255er, 67 254er und 322 253er in 11 Stunden.

Ich hatte für unterschiedliche Suchtiefen depth ausprobiert, ab welcher Versuchszahl bei Tiefe d < depth man die Suche abbrechen sollte, um die durchschnittliche Zeit in der Tiefe depth erreicht wird zu minimieren. Das geht für Tiefe d < 250 ganz gut, dann wird es zeitaufwändig. Ich habe die Optimierung nur grob von Hand durchgeführt, das Verfahren sollte sich aber leicht automatisieren lassen. Besonders evolutionäre Verfahren könnten sich dafür eignen. Anstelle von 3 255ern in 23 Stunden sind es jetzt 12 255er in 11 Stunden, also eine wichtige Verbesserung. Wenn Ingos These der ca. 10 255er pro Lösung korrekt wäre, dann wären ca. 10 Stunden die durchschnittliche Lösungszeit für das 4-Farben Problem.



drdwo
07.07.2016, 10:22

Als Antwort auf den Beitrag von drdwo

Re: potentielle Lösung des 4-Farben Problems zur Verifikation

Sorry zwei kleine Korrekturen


mit der eine Suchtiefe [247-256] erreicht wurde

soll heissen "mit der eine Suchtiefe [237-256] erreicht wurde"


Ich hatte für unterschiedliche Suchtiefen depth ausprobiert, ab welcher Versuchszahl bei Tiefe d < depth

soll heissen "Ich hatte für unterschiedliche Suchtiefen depth ausprobiert, ab welcher Versuchszahl bei bisher maximal erreichter Tiefe d < depth"



16 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: