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.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


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)

25 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

cimddwc
24.06.2016, 23:26

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Permalink

1000steine-Code

BBCode

HTML


Nun, ich werd' nächste Woche noch weiterrechnen lassen (übers Wochenende bleibt der PC aus), 253 Steine hat das 4er-Programm mittlerweile erreicht; Zwischenstand beim 3er sind 4,2 Mio. Lösungen.

(Rechenzeit kann ich leider nicht angeben, weil die ausgegebene sich dummerweise auf die Uhrzeit des Starts bezieht...)

Grüße,
Andreas



IngoAlthoefer
25.06.2016, 10:06

Als Antwort auf den Beitrag von cimddwc

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Andreas,

cimddwc hat geschrieben:

Nun, ich werd' nächste Woche noch weiterrechnen lassen
(übers Wochenende bleibt der PC aus),

sehr löblicher Vorsatz.


253 Steine hat das 4er-Programm mittlerweile erreicht;

Die drei fehlenden schafft Deine Kiste auch noch!

Ingo
(ist in der kommenden Woche grossteils offline; wegen
der Computer-Spiele-Olympiade in Leiden(NL))


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Sylvius
25.06.2016, 15:44

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

Hi.

Interessant, da juckt es mich fast wirklich mir die Teile für den Nachbau zu besorgen.

Eine Frage aber:

Kirk schrieb:

...stimmt, die Ausrichtung der weißen Kreuze muß bei allen Steinen identisch sein, denn sonst paßt es nicht...


Wieso? Ohne auf die Farben zu achten, kann man die weißen Kreuze doch durchaus so zusammenlegen, dass sich ein 4x4 ergibt ohne dass die Kreuze gleich ausgerichtet sind.

MfG

Sylvius



IngoAlthoefer
25.06.2016, 22:55

Als Antwort auf den Beitrag von Sylvius

Re: Puzzle mit 4x4 Teilen

Hallo Sylvius,

Sylvius hat geschrieben:

Eine Frage aber:

Kirk schrieb:
...stimmt, die Ausrichtung der weißen Kreuze muß bei allen
Steinen identisch sein, denn sonst paßt es nicht...

Wieso? Ohne auf die Farben zu achten, kann man die weißen Kreuze doch
durchaus so zusammenlegen, dass sich ein 4x4 ergibt ohne dass die
Kreuze gleich ausgerichtet sind.

Du hast recht. Es gibt dann sogar mehr als die eigentlichen
800 Lösungen. Habe aber vergessen, wie viele genau.

Das ursprüngliche Puzzle (aus den 1950ern) verlangte aber die "enge" Auslegung der Regeln.

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Kirk
25.06.2016, 22:55

Als Antwort auf den Beitrag von Sylvius

Re: Puzzle mit 4x4 Teilen

Sylvius hat geschrieben:

Ohne auf die Farben zu achten, kann man die weißen Kreuze doch durchaus so zusammenlegen, dass sich ein 4x4 ergibt ohne dass die Kreuze gleich ausgerichtet sind.


Hallo Sylvius,

gerade wollte ich zu einer meiner epischen Begründungen ansetzen, warum ich Recht habe, bis ich mir überlegte, es nochmal selbst auszuprobieren. Das erstaunliche Ergebnis: Ja, Du hast Recht! Es gibt tatsächlich noch eine 2. Möglichkeit, die Teile im Quadrat anzuordnen, wobei natürlich die Größen der farbigen Flächen zwischen 2x2 und 4x4 schwanken. Da aber mein Ergebnis von 800 Lösungen von Ingo bestätigt wurde, gehe ich davon aus, daß die einheitliche Ausrichtung implizit Bestandteil des Puzzles ist. Ich würde mich aber freuen, wenn Du eine Lösung mit der 2. Anordnungsvariante posten würdest.

Gruß

Thomas


\\//_ Build long and ℘rosper!


Sylvius
25.06.2016, 23:52

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen

Kirk hat geschrieben:

Sylvius hat geschrieben:
Ohne auf die Farben zu achten, kann man die weißen Kreuze doch durchaus so zusammenlegen, dass sich ein 4x4 ergibt ohne dass die Kreuze gleich ausgerichtet sind.


Hallo Sylvius,

gerade wollte ich zu einer meiner epischen Begründungen ansetzen, warum ich Recht habe, bis ich mir überlegte, es nochmal selbst auszuprobieren. Das erstaunliche Ergebnis: Ja, Du hast Recht! Es gibt tatsächlich noch eine 2. Möglichkeit, die Teile im Quadrat anzuordnen, wobei natürlich die Größen der farbigen Flächen zwischen 2x2 und 4x4 schwanken. Da aber mein Ergebnis von 800 Lösungen von Ingo bestätigt wurde, gehe ich davon aus, daß die einheitliche Ausrichtung implizit Bestandteil des Puzzles ist. Ich würde mich aber freuen, wenn Du eine Lösung mit der 2. Anordnungsvariante posten würdest.

Gruß

Thomas


Hi Kirk,

leider reichts da bei mir mit meinen Kenntnissen beiweiten nicht für. Mir war nur nach einem kurzen Blick klar, das ich ein Teil aus der "Normalausrichtung" nehmen kann (rein jetzt auf die weißen Kreuze Bezogen), dieses um 90, 180 und 270 drehen könnte und an der Spitze zusammen setzen könnte. Daraus habe ich dann ein 2x2 bekommen woraus man 4 wiederum zu einem 4x4 zusammensetzen konnte. Durch eine weitere Zeilen- und Spaltenvertauschenung (oben abnehmen und unten dransetzen + links eine wegnehmen und rechts dransetzen), kriegt man dann eine 3. Anordnbung, die man wiederum um 90, 180 und 270 drehen könnte. Wie gesagt Lösungen habe ich dafür nicht, weil es dafür nicht bei mir reicht.
Ich war eigentlich in gutem Glauben davon ausgegangen, dass du vielleicht einen Grund wüsstest, warum es für die anderen Anordnung keine Lösung gibt. (Analog des bekannten Geschicklichkeitspiels, wo man in einem 4x4 Quadrat 15 Plätchen it Zahlen und ein Freiraum hat und man durch verschieben die Zahlen in Reihenfolge bringen kann. Setzt man dort die Zahlen willkürlich ein, kann man ja auch sofort bestimmen, ob das Rätsel in der From lösbar ist oder nicht).

MfG
Sylvius



Zypper
02.07.2016, 15:09

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

Hi, Ingo,

vielen Dank für die Idee. Hab sie gleich abgekupfert in rot/schwarz und auf Platten bzw. auf "Unten-Drunter-Fliesen" gelegt. So ein Spiel kann ich zur Erweiterung meines Repertoires immer brauchen, denn ich bin ja immer auf der Suche nach etwas, mit dem man Ausstellungsgäste unterhalten kann. Ob und welche Lösungen große und kleine Gäste mit diesem neuen Spiel finden werden, ist dabei völlig unerheblich: Es geht um die Faszination, das von dem Material ausgeht. Denn die allermeisten sind völlig überrascht, wenn sie sehen, was man auch daraus machen kann.

Hinzu kam, dass ich noch ein Kästchen übrig hatte, in das genau 16 Kärtchen passen.

Bis bald
Andreas


Mit Gruß und Dank
Zypper

[image]


Über das Projekt 366 bei FlixBrix
Zypper im LEGO-Intranet
Zypper im SWR-Treffpunkt "Sammelleidenschaft" ab Minute 8.
Zypper bei flickr
Zyppers Werke in einer Diashow 1989-2020


IngoAlthoefer
04.07.2016, 09:17

Als Antwort auf den Beitrag von Zypper

Re: Puzzle mit 4x4 Teilen

Hallo Andreas,

Zypper hat geschrieben:

vielen Dank für die Idee. Hab sie gleich abgekupfert in
rot/schwarz und auf Platten bzw. auf "Unten-Drunter-Fliesen" gelegt.
So ein Spiel kann ich zur Erweiterung

meines Repertoires
immer brauchen, denn ich bin ja immer auf der
Suche nach etwas, mit dem man Ausstellungsgäste unterhalten kann...

Du magst es nicht glauben. "Mein" Puzzle (ursprünglich als Pen-and-Paper-Version
kreiert von C.J. Bouwkamp) hatte ich schon im Dezember 2011 gebaut und damals
als Adventsrätsel in der Computerspiele-Szene genutzt. Die Teile lagen vergessen
im Regal. Als ich Deinen Beitrag im Mai las, erinnerte ich mich wieder.

Ist doch toll, wie wir uns wechselseitig befruchten.

Dir und allen anderen eine gute Woche,
Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


IngoAlthoefer
04.07.2016, 09:27

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (Update)

Hallo, Ihr Tüftler gross und klein,

cimddwc hat geschrieben:

Nun, ich werd' nächste Woche noch weiterrechnen lassen
(übers Wochenende bleibt der PC aus),

253 Steine hat das 4er-Programm mittlerweile erreicht;

jetzt habe ich meinen Kumpel Dietmar Wolz aus der Astrophysik-Szene
auf das Puzzle hingewiesen. Er hat (mit seinem Hintergrundwissen aus
den beiden Eternity-Puzzles) ein schnelles Programm geschrieben, was
inzwischen auch einen ersten 254er (bei 4 Farben) gefunden hat. 253er
liefert sein Prog im 10-Minuten-Takt.
Diemar verwendet dabei auch eine Heuristik, die davon ausgeht, dass
sich im Gesamtbild "Klumpen" finden sollten, in denen einzelne der Farben
dominieren.

Mal schauen, ob (und von wem) ein Vorstoss zu 255 und 256 gelingt.

Frohes Puzzeln,
Ingo.

********************************************************
Material zum ursprünglichen Problem mit "nur" zwei Farben findet
sich in einem Online-Artikel von Jacques Haubrich:
http://2000clicks.com/mat...esJacquesHaubrich.aspx
Dort ist auch die Anzahl 800 genannt, die schon 1970 erstmalig ermittelt
worden war. (Dank an Torsten Sillke, der mich auf die Quelle hinwies.)


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
04.07.2016, 10:12

Als Antwort auf den Beitrag von cimddwc

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo,
Ingo hat mich vor ein paar Tagen auf das Lego Puzzle aufmerksam gemacht. Wir kennen uns schon lange, seit ich mich vor vielen Jahren mit dem Eternity-Puzzle beschäftigt habe https://de.wikipedia.org/wiki/Eternity-Puzzle. Davon gibt es eine neue Variante, Eternity 2, und die hat sehr viel Ähnlichkeit mit dem 4-Farben-Lego Problem. Aus diesem Grund empfehle ich http://cs.brown.edu/peopl...Papers/v3/eternity.pdf , viele Ideen daraus lassen sich auf das Lego-Problem übertragen.

Die Reihe-für-Reihe Strategie ist für Eternity 2 sehr gut. Beim Lego-Problem gibt es im Gegensatz zu Eternity 2 keinen definierten "Rand", füllen wir die z.B. die erste Reihe, haben wir fast nur 1-Seiten-Constraints. Eine Strategie, die immer größere Quadrate beginnend in einer Ecke konstruiert hat schneller 2-Seiten-Constraints und müsste theoretisch besser sein.

Das lässt sich mit dem 2-Farben-Lego Problem leicht beweisen, statt ca. 80000 haben wir nur noch ca. 70000 Versuche. Der Vorteil für das 4-Farben Lego sollte größer sein.

Aus Eternity 1 haben wir gelernt, das es sich lohnt, am Anfang die Suche einzuschränken, wenn dafür am Schluss "besser zusammenpassende" Teile übrigbleiben. Nehmen wir z.B. das 9x9er 3-Farben Problem:

Wenn wir am Anfang nur die 16 Teile mit den ersten beiden Farben verbauen (Eine Lösung des 4x4er 2-Farben Problems) bleiben nur Teile übrig, die alle die dritte Farbe haben und theoretisch mit höherer Wahrscheinlichkeit zusammenpassen. Das ganze lässt sich analog auf das 4-Farben Problem mit vordefiniertem 9x9er übertragen.

Auch die Frage, ob es sich lohnt in Assembler zu programmieren, oder ob eine Programmiersprache wie z.B. Java reicht, war vor 16 Jahren in Bezug auf Eternity 1 schon aktuell. Nur 3 Personen konnten das Puzzle lösen, einer davon (Günter Stertenbrink) benutzte Assembler. Allerdings war dann später ein Java Programm in der Lage, schneller weitere Lösungen zu berechnen.

Für das Lego 2-Color Problem haben wir 2ms für 80000 Versuche für Assembler, mein Java-Programm braucht 2.5 ms. Da man in Java leichter neue Ideen (wie die oben beschriebenen) ausprobieren kann, scheint auch hier der Assembler-Vorteil überschaubar, zumal wir es heute in der Regel mit Multi-Thread Prozessoren zu tun haben. Die Parallelisierung der Suche lässt sich in Assembler nur schwer realisieren.

Mir gefällt das Lego-Problem besonders, weil es neben dem "schwierigen" 4-Farben Problem die lösbare 3-Farben Variante gibt. Die kann man benutzen, um Ideen in Bezug auf Verbesserungen des Suchverfahrens zu testen.

Für das 4-Farben Problem habe ich bis jetzt übrigens auch nur mehrere 254er Teillösungen gefunden. Durch betrachten der Suchergebnisse in Tiefe 79-81 des 3-Farben-Problems versuche ich jetzt, Ideen für eine Verbesserung zu finden. 253 Teile war übrigens auch mein bestes Ergebnis mit der einfachen Reihe-für-Reihe Strategie.

Grüsse Dietmar



43 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: