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)

42 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

IngoAlthoefer
05.07.2016, 08:47

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Permalink

1000steine-Code

BBCode

HTML


Hallo Dietmar,

danke für die sehr schön formatierte 3er-Lösung.
In der Ecke links oben (4x4 Teile) sieht man sehr
gut, wie Du mit einer 0-1-Lösung begonnen hast.

Gruss, Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
05.07.2016, 10:13

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Also war die 3er korrekt? Hoffentlich keine doppelten Teile mehr. Es gibt schlechte Nachrichten - der korrigierte Algorithmus ist jetzt doch erheblich langsamer, heute Nacht haben meine Rechner nur 4 254er gefunden, obwohl ich neben meinen 3 Hauptrechnern noch 2 Reserve-Maschinen aktiviert hatte. Zusammen schaffen sie auf insgesamt 52 parallelen Threads knapp 1E9 Versuche pro Sekunde. Da der Sprung 253->254 jetzt viel schwerer ist, vermute ich das auch für die zwei verbleibenden Sprünge. Hier ein 254er

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33 33 30 03 33 30 03 31 13 33 30 01 13 30 03 32
12 22 23 32 23 30 03 32 20 03 33 30 03 32 23 30

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

Vielleicht inspiriert die jemand zu einer Verbesserungsidee. Womöglich schafft man es irgendwie, Teile die am Schluss mit einer höheren Wahrscheinlichkeit zusammenpassen vorher mit einer geringeren Wahrscheinlichkeit zu legen. Das vordefinierte 9x9er geht in diese Richtung, vielleicht geht aber noch mehr.



cimddwc
05.07.2016, 11:08

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

drdwo hat geschrieben:

Es gibt schlechte Nachrichten - der korrigierte Algorithmus ist jetzt doch erheblich langsamer, heute Nacht haben meine Rechner nur 4 254er gefunden, obwohl ich neben meinen 3 Hauptrechnern noch 2 Reserve-Maschinen aktiviert hatte. Zusammen schaffen sie auf insgesamt 52 parallelen Threads knapp 1E9 Versuche pro Sekunde.

Dann bin ich ja beruhigt, dass mein simples Programm nach einer Woche Mo.-Fr. tagsüber single-threaded in einer virtuellen Maschine immer noch nicht mehr als 253 Steine verbaut hat.

Die 3x3-Variante meint übrigens, derzeit 23,6 Mio. Lösungen gefunden zu haben, im Sekundentakt kommen immer noch einige bis ein paar Dutzend dazu.

Grüße,
Andreas



IngoAlthoefer
05.07.2016, 15:03

Als Antwort auf den Beitrag von drdwo

Puzzle mit 9x9 Teilen (kompakte Darstellung)

Hallo Dietmar,

Deine 9x9-Lösung habe ich jetzt auf Korrektheit geprüft - sie ist
tatsächlich eine. Und ich habe sie als kompaktes Mosaik realisiert.
Wegen des Overlaps braucht man tatsächlich nur die 10x10 Einzel-Einträge,
statt der 9x9 Vierer.

drdwo hat geschrieben:

00 01 10 01 12 20 02 22 20
00 00 00 01 10 00 02 22 20

00 00 00 01 10 00 02 22 20
10 01 11 10 02 20 01 11 10

10 01 11 10 02 20 01 11 10
11 11 11 10 00 01 12 22 21

11 11 11 10 00 01 12 22 21
01 10 00 01 12 21 11 10 02

01 10 00 01 12 21 11 10 02
02 20 02 20 00 00 02 22 21

02 20 02 20 00 00 02 22 21
11 11 10 02 22 21 12 21 11

11 11 10 02 22 21 12 21 11
12 21 12 20 02 21 12 22 20

12 21 12 20 02 21 12 22 20
21 12 22 22 22 20 01 12 21

21 12 22 22 22 20 01 12 21
10 02 20 00 01 12 22 20 01

Die Bedeutung der Farben ist
schwarz=0, orange=1, rot=2.

[image]


Das Mosaik ohne Markierungen.

[image]


Markiert ist die
0 1
0 0
links oben.


[image]


Markiert ist die
1 0
0 0
links oben.


[image]


Markiert ist die
0 2
0 2
rechts oben.

In dem 10x10-Mosaik kommt jedes dreifarbige 2x2-Muster genau einmal vor!

Analog wird man eine hoffentlich bald kommende 16x16-Lösung für das 4-Farben-Muster
durch ein kompaktes 17x17-Gitter darstellen können.

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Eisbär
05.07.2016, 15:19

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 9x9 Teilen (kompakte Darstellung)

Liebär Ingo!

Gehört das nich so:

[image]

?

Meine Kollegin hat schon die Jalousien für den Feyerahmt runtergetan, ich sehe also da draußen, nicht, was gerade weht.

Reinweiße Grüße
M.a



IngoAlthoefer
05.07.2016, 16:10

Als Antwort auf den Beitrag von Eisbär

Re: Puzzle mit 9x9 Teilen (kompakte Darstellung)

Lieber Mich.a,

Eisbär hat geschrieben:


Gehört das nich so:

[image]




lass es mich so sagen: mancher hat Farbgefühl,
manch anderer hält sich an seiner Nationalflagge fest.

Wer unsicher ist, kann gerne in der Brettspielszene bei den angesagten
Verlagen schauen, welche Farben in ihren Spielen vorkommen.

Beispiel:
Blokus mit den Basisfarben gelb, rot, blau und grün ist ziemlich daneben.
Blokus Duo (da hatten sie endlich einen Designer ins Team genommen) dagegen
super in orange und lila.

Mit farbenfrohen und stilechten Sinnen,
Ingo.

PS. Seine Basisfarben hatte LEGO wohl in Anlehnung an den
erfolgreichen Herrn Mondrian gewählt, auch wenn der gar kein Däne war


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
05.07.2016, 18:55

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 9x9 Teilen (kompakte Darstellung)

Vielen Dank für das Überprüfen. Damit sollte meine 4-Farben Suche eigentlich auch fehlerfrei sein. Ca. 8 254er, aber noch keine Lösung.
Um den Vorteil des vordefinierten 9x9ers mit 3 Farben auszubauen, habe ich das Verfahren so verändert, das er auch später noch zuerst Teile legt, die möglichst wenige Farben haben. Mir ist noch nicht ganz klar, warum das hilft - habe es empirisch mit dem 3-Farben Problem getestet. Könnte man die Teile wie bei Eternity2 drehen, dann wäre es am Schluss definitiv gut, viele Farben zu haben - wir haben ja keinen Rand und hätten mehr Variationen die passen könnten. Jedenfalls scheint es jetzt wieder etwas mehr 254er zu geben, allerdings längst nicht so viele wie mit der fehlerhaften Suche von vorgestern.



drdwo
05.07.2016, 19:09

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 9x9 Teilen (kompakte Darstellung)

Langsam aber sicher kommen wir der Sache näher:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21 12 23 31 12 20 02 23 32 23 32 21 13 30 02 23
03 32 23 30 03 30 03 30 03 32 23 30 01 13 30 03

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



IngoAlthoefer
05.07.2016, 20:20

Als Antwort auf den Beitrag von drdwo

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

Glückwunsch zum 255er!

Ingo (überlegt schon mal grob, wie er den 256er als
kompaktes 17x17-Gitter umsetzt - auch mit Farben, die
von mich.a abgesegnet werden...).


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
06.07.2016, 09:26

Als Antwort auf den Beitrag von IngoAlthoefer

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

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

Ein schlaueres Verfahren schafft ein 253er sicher in weniger Versuchen. Die spannende Frage ist, ob es auch mehr 253er
in einem definierten Zeitraum auf gleicher Hardware schafft.

Komisch ist, das die drei 255er alle auf einem (von 5) Rechnern gefunden wurden. Die Wahrscheinlichkeit dafür ist glaube
ich relativ gering. Deshalb vermutete ich zunächst, das ich auf diesem Rechner versehentlich irgendetwas anders gemacht habe -
habe aber nichts gefunden.

Andreas hatte geschrieben:

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.


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.



26 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: