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:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
doktorjoerg , Custer , Cran , Seeteddy , Legomichel , Dirk1313 , renrew , Legobecker , Plastik , MARPSCH , fannie1981 , Lukutus , cimddwc , doe , uefchen , Titus , naseneis , nvneuss , JuL (19 Mitglieder)
Liebär Ingo!
Lieber mich.a,
Eisbär hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
LIeber Mich.a,
bitte vorsichtig sein, sonst verschreckst Du noch den Dietmar.
Ingo.
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
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.
Sorry zwei kleine Korrekturen
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)
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
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