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)

60 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

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"



IngoAlthoefer
07.07.2016, 19:31

Als Antwort auf den Beitrag von drdwo

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

Hallo Dietmar,

hatte einen harten Tag auf Arbeit (letzte Vorlesungswoche).
Komme deshalb erst jetzt ans Internet. Deine Lösung schaue
ich mir nachher während des Ballspiels an.
Dank auch für die Trefferstatistik!

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
08.07.2016, 01:10

Als Antwort auf den Beitrag von IngoAlthoefer

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

Abends keine Überraschung - sondern die erwartete 2. Lösung

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

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

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

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

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

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

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

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

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

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

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

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

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

00 00 01 11 11 13 31 13 31 13 33 31 13 31 13 32
31 13 31 13 33 31 11 11 10 00 03 31 12 20 01 11

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

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



drdwo
08.07.2016, 01:51

Als Antwort auf den Beitrag von IngoAlthoefer

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

Und auch noch eine dritte:

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

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

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

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

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

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

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

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

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

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

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

22 22 22 22 22 22 22 21 13 32 21 12 23 32 23 30
31 13 30 03 32 23 33 31 12 23 33 31 12 21 13 33

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

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

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

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



drdwo
08.07.2016, 07:35

Als Antwort auf den Beitrag von IngoAlthoefer

Aller guten Dinge sind 4

Die 4. Lösung wieder mit erreichten Suchtiefen aller Rechner in ca 132000 Sekunden also geschätzt 132000*9.5E8 = 1.25E14 Versuche.

[106743, 91989, 77449, 65161, 64715, 62700, 60265, 54543, 49248, 39345, 26459, 14481, 8417, 3620, 1967, 688, 197, 37, 2, 1]

[95884, 82998, 69709, 58632, 58276, 56464, 54195, 49033, 44206, 35228, 23769, 12898, 7576, 3267, 1815, 635, 202, 29, 7, 1]

[107323, 92722, 77987, 65592, 65205, 63168, 60620, 54886, 49410, 39202, 26278, 14484, 8465, 3620, 1983, 681, 207, 43, 9, 1]

[76380, 65866, 55344, 46575, 46301, 44826, 43059, 39048, 35201, 28160, 18896, 10255, 5959, 2491, 1343, 466, 155, 24, 4, 1]

[75935, 65612, 55190, 46344, 46022, 44584, 42761, 38703, 34888, 27817, 18596, 10281, 6010, 2579, 1411, 449, 141, 26, 1, 0]


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



IngoAlthoefer
08.07.2016, 12:53

Als Antwort auf den Beitrag von drdwo

Re: Aller guten Dinge sind 4

Hallo Dietmar,

super. Schön ist, wie Du in allen Lösungen links oben
mit der 0,1- Population anfängst (4x4), dann übergehst
zur 0,1,2-Population (9x9), und erst danach die 3er einsteigen.

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
08.07.2016, 15:44

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Aller guten Dinge sind 4

wie Du in allen Lösungen links oben
mit der 0,1- Population anfängst (4x4), dann übergehst
zur 0,1,2-Population (9x9), und erst danach die 3er einsteigen.

Das ist ja Teil der Strategie und hat keine ästhetischen Gründe.
In den Postings weiter oben habe ich alle Aspekte dieser Strategie beschrieben.
Aber schön, wenn es dir gefällt.

Bin über das Wochenende unterwegs und habe vorher alle meine Rechner abgeschaltet,
es macht ja auch keinen Sinn mit dieser Methode weiterzurechnen - wir wissen ja
recht genau was sie kann und haben genügend Informationen um sie mit anderen Verfahren
zu vergleichen.



drdwo
11.07.2016, 19:42

Als Antwort auf den Beitrag von IngoAlthoefer

Wie viele Versuche braucht man für alle Lösungen?

Hier ist noch ein schöner Artikel über das verwandte Eternity II puzzle http://www.rookiemag.com/...ltbte-eternity-puzzle/

Hätte man dieses Puzzle rechtzeitig gelöst, so hätte man 2 Millionen englische Pfund gewinnen können. Auf https://en.wikipedia.org/wiki/Eternity_II_puzzle kann man nachlesen, das es für die größte partielle Lösung "467 matching edges out of 480" immerhin 10000$ gab.

Es is relativ schwer abzuschätzen, wie viele Versuche man benötigt, um eine erste Lösung zu finden. Das gilt aber nicht für die Abschätzung der Zahl der Versuche die man benötigt, um alle Lösungen zu bestimmen - die Größe des Suchraums.

Man legt einfach jeweils ein zufällig passendes Teil und merkt sich die Zahl der Möglichkeiten. Haben wir zum Beispiel beim Legen des sechsten Teils durchschnittlich 2 Möglichkeiten dann verzweigt sich der Suchbaum hier um Faktor 2. Hat man alle Verzweigungsfaktoren abgeschätzt, kann man die Größe des gesamten Baums schätzen. Einen Trick braucht man noch: Wenn kein Teil passt, dann müssen wir damit es weiter geht ein zufälliges möglichst gut passendes Teil (eine Seite passt nicht) nehmen. Und wir müssen das Ganze oft wiederholen und Mittelwerte bilden.

Beim 2-Farben Lego Problem ergibt sich:

Diagonal Strategie: 8.1E4 Versuche

Reihe für Reihe Strategie: 9.6E4 Versuche

In der Realität haben wir ca. 10-15% weniger Versuche, aber die Abschätzung funktioniert ganz gut.

Schon beim 3-Farben Lego-Problem haben wir keine realen Zahlen mehr zum Vergleich, es ergeben sich:

Diagonal Strategie: 1.8E26 Versuche
Reihe für Reihe Strategie: 6.6E26 Versuche

Für das 4-Farben Lego Problem sind es:

Diagonal Strategie: 3.2E93 Versuche
Reihe für Reihe Strategie: 5.0E96 Versuche

Für das Eternity II Puzzle sind es aber nur

Diagonal Strategie: 4.0E51 Versuche
Reihe für Reihe Strategie: 7.6E48 Versuche

Das Puzzle hat einen definierten Rand, deshalb ist hier die Reihe für Reihe Strategie besser.

Warum haben wir jetzt für das 4-Farben Lego Problem Lösungen, aber nicht für das Eternity-II Problem?

Es gibt viel weniger Lösungen für Eternity-II, deshalb ist die Berechnung einer einzelnen
Lösung hier um viele Größenordnungen schwieriger.



IngoAlthoefer
14.07.2016, 20:05

Als Antwort auf den Beitrag von drdwo

Kombinatorik-Rätsel auf LEGO-Basis

Hallo Dietmar,

danke für Deine interessanten Erläuterungen und Einordnungen
zu den verschiedenen Puzzles.

... Es ist relativ schwer abzuschätzen, wie viele Versuche
man benötigt, um eine erste Lösung zu finden. Das gilt aber nicht
für die Abschätzung der Zahl der Versuche die man benötigt, um
alle Lösungen zu bestimmen - die Größe des Suchraums... [/quote]

Für das 4-Farben Lego Problem sind es:
Diagonal Strategie: 3.2E93 Versuche
Reihe für Reihe Strategie: 5.0E96 Versuche

Für das Eternity II Puzzle sind es aber nur
Diagonal Strategie: 4.0E51 Versuche
Reihe für Reihe Strategie: 7.6E48 Versuche

Allgemein ist LEGO eine wunderbare Umwelt für kombinatorische
Puzzles und Probleme. Schon das Auszählen der Möglichkeiten,
wie man 6 oder allgemeiner k Steine einer Farbe vom 4x2-Typ
zusammensetzen kann, hat ja zu interessanten Mathe-Papers geführt.

Es sollte aber noch viel mehr interessante Kombinatorik-Fragen im
Zusammenhang mit LEGO-Komplexen geben. Wem welche ein- oder auffallen,
kann sich gerne bei mir melden. Ich kann - in diesem Zusammenhang -
auch immer spannende Themen für Staatsexamens-Arbeiten von Mathe-
Lehramts-Studenten gebrauchen.

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


8 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: