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)
Lieber Ingo!
Hm. Ich fürchte, meine logischen Fähigkeiten sind unzureichend. Man soll also alle Teile zusammenlegen, nicht Domino spielen? In welcher Façon soll das Zusammengelegte denn sein? Quadrat?
Außerdem befürchte ich, daß das Ergebnis der norgewischen Flagge allzu ähnlich werden könnte, daher muß ich dies Puzzle aus patriotischen Gründen sein lassen. Ein Blick aus meinem Bürofenster ist da schlimm genug: vier Fahnenmasten allein schon am Rathaus und nur am 6. Februar ein angenehmer Anblick.
Lieber Micha,
Eisbär hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
IngoAlthoefer hat geschrieben:
Hallo Andreas,
cimddwc hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Hallo Ingo,
\\//_ Build long and ℘rosper!
Hallo Thomas,
Kirk hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Kirk
21.06.2016, 19:50
Als Antwort auf den Beitrag von IngoAlthoefer
Editiert von
Kirk
21.06.2016, 19:55
Hallo Ingo,
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
Hallo Thomas,
Kirk hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Liebär Ingo!
Hm.
Man nehme die Teile und lege sie zusammen, so daß herauskommt:
Hallo Mich.a,
Eisbär hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
IngoAlthoefer hat geschrieben:
Liebär Ingo!
Also man kann beweisen, daß es keine Formel gibt, um dieses Puzzle (oder alle Puzzles?) zu berechnen, aber anstatt die Teile per Hand zusammenzulegen, berechnet man das Puzzle per Computer, aber mit ohne Formel? Isses n Wunder, daß die EDVler in's Schwitzen kommen?
Stimme aus dem OFF: Ingo schrieb: es sei beweisbär, nicht, daß man es beweisen könne. Das sog. Althöfer'sche Paradoxon.
Zu Deinen Zetteln ist zu bemerken, daß die Zahlen nicht in steigender Reihenfolge angeordnet sind. So wie in Büchern die Buchstaben nicht alphabetisch nacheinander kommen.
Es fehlt auch die Anordnung nach senkrechten Spalten. Das ist die, die unsere Leser immer durcheinanderbringt: sie bemerken die Trennwände zwischen den RegalABSchnitten nicht und hopsen somit von Hamsun zu Hemingway. „Sind denn alle Hansens ausgeliehen?“
Im übrigen bin ich der unerforschlichen Meinung, ein Puzzle mit 10 hoch irgendwas (eine ganze, endliche Zahl*) Lösungen sei nicht ewig, denn 10 hoch irgendwas sei endlich.
*Evt. natürlich, positiv etc pp. Sagen wir: eins, zwei, drei, viele. Bis 20, dann isses mit den Händen und Füßen ja meistens vorbei. Und wer kann so weit zählen?
Polydaktyle Grüße
M.a
Hallo Ingo,
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
-jc- hat geschrieben:
Bricoon hat geschrieben:
\\//_ Build long and ℘rosper!
Hallo,
jetzt hat's mich auch gepackt und ich hab auch ein Progrämmchen geschrieben (bzw. 3 Varianten, jeweils angepasst).
Vorgehensweise:
- 2 Listen erstellen, in denen für jeden Stein angegeben ist, welcher rechte bzw. untere Nachbar möglich ist
- nach und nach Felder durchgehen, bei möglichen Steinen weiterprobieren mit den nächsten Feldern, ansonsten zurück. (Ist das Backtracking?)
Und das ganze schön optimiert in x86-Assembler. Die 2-Farb-Variante (dafür reichen die normalen 32-Bit-Register (sogar 16 Bit würden reichen)) findet die 800 Lösungen nach ca. 80.000 Versuchen in ca. 2 Millisekunden.
Die 3- und 4-Farb-Variante benutzen die 256-Bit-Register von AVX2 - allerdings mit dem Problem, dass die Suche des nächsten möglichen Steins nicht so schön effizient ist wie mit den normalen Registern. Oder kennt jemand eine gute BSF-Variante für AVX2-ymm-Register?
Wobei ich sagen muss, dass das recht schnelle Versuche waren - ich hab zwar einige gefundene (Teil-)Lösungen kontrolliert, kann mir aber gerade bei den 3- und 4-Farb-Varianten nicht wirklich 100% sicher sein, dass alles stimmt... theoretisch sollte es jedenfalls.
Das 3-Farben-Programm läuft noch, nach 41 Minuten war's bei 560.000 Lösungen und 100 Mrd. Versuchen angelangt. Na hoffentlich stimmt das auch...
Das 4-Farben-Programm läuft noch nicht so lange, das hat nach 7,5 Sekunden schon 246 Steine nach 350 Mio. Versuchen verbaut und eben nach ca. 7,5 Minuten waren's 250 Steine nach 19,8 Mrd Versuchen. Aber noch keine komplette Lösung.
Grüße,
Andreas
Hallo Andreas,
cimddwc hat geschrieben:
\\//_ Build long and ℘rosper!
Hallo,
Ich werd morgen nochmal weitere Lösungen unter die Lupe nehmen, ob da nicht zu viele dabei sind. Jedenfalls schläft mein Rechner über Nacht, der letzte Stand bei 4 Farben war nach 184min 252 Steine bei 482 Mrd Versuchen.
Grüße,
Andreas
Mir ist grad noch was eingefallen: ich glaub, ich zähl die Versuche falsch. Der Zähler wird erhöht, wenn in einem Feld n kein Stein mehr möglich ist (sodass das eben als Versuch fürs Feld n-1 zählt). Aber beim Zurückgehen, wenn das auch die letzte Möglichkeit für n-1 war und es weiter zu n-2 zurückgeht, wird er nochmal erhöht, u.s.w., und das wäre dann immer etwas zu viel...
Grüße,
Andreas
cimddwc hat geschrieben:
\\//_ Build long and ℘rosper!
Ich geb's auf!
Nach etlichen Milliarden Versuchen habe ich über 21.000 Lösungen für das 3-Farb-Puzzel gefunden, aber keine einzige für 4 Farben. Mein bestes Ergebnis waren 237 von 256 Teilen. Nachdem ich weiter oben in diesem Thread mal die Kombinationsmöglichkeiten für 2 Farben durchgerechnet hatte, wage ich nicht einmal ansatzweise darüber nachzudenken, wie viele Nullen wohl die Zahl der Versuche haben mag, die sich bei 3 und 4 Farben ergeben... Selbst abzüglich der übersprungen Möglichkeiten übersteigt dies meine Kapazitäten, um in einem überschaubaren Zeitraum zu einem endgültigen Ergebnis zu kommen.
\\//_ Build long and ℘rosper!
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
Hallo Andreas,
cimddwc hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Hi.
Interessant, da juckt es mich fast wirklich mir die Teile für den Nachbau zu besorgen.
Eine Frage aber:
Kirk schrieb:
Hallo Sylvius,
Sylvius hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Sylvius hat geschrieben:
\\//_ Build long and ℘rosper!
Kirk hat geschrieben:
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
Hallo Andreas,
Zypper hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Hallo, Ihr Tüftler gross und klein,
cimddwc hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
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
Hallo Dietmar,
willkommen bei den AFoLs (adult fans of LEGO).
Wenn Du Dich etwas umschaust, wirst Du nicht nur
1000 LEGO-Steine entdecken, sondern auch 1000 Köpfe und
1000 Ideen.
Meine Spezialität ist es, aus wenigen Teilen irgendetwas
ganz anderes zu bauen. Siehe etwa
http://www.1000steine.de/...amp;id=360048#id360048
Gruss, Ingo.
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Noch ein paar Ergänzungen/Hinweise:
1) Warum ist es gut, möglichst früh starke Constraints zu haben?
Stärkere Constraints versursachen einen kleineren Suchbaum. Um so früher, um so kleiner.
Beispiel: Stellen wir uns einen Baum der Höhe 10 mit zwei Kindern an der Wurzel vor,
die Knoten der anderen Ebenen haben je ein Kind. Das sind 19 Knoten. Ist die Verzweigung erst auf der neunten Ebene,
sind es 11 Knoten. Es ist also besser, die Suche möglichst früh einzuschränken.
2) Abbruch der Suche
Wir erzeugen viele zufällige 3-Farben Lösungen und zählen jeweils die Versuche bis wir Tiefe 78 erreicht haben, um ein Gefühl
dafür zu bekommen, wann es sich lohnt bei dieser Suchtiefe die Suche abzubrechen.
Die Zahl der Versuche in einer Suchtiefe variiert sehr stark von Lösung zu Lösung.
Stellen wir zum Beispiel fest, das sich bei 10% der Lösungen bei Suchtiefe 78 die Zahl der Versuche weniger als 2% der durchschnittlichen
Versuchszahl an dieser Tiefe ergibt, dann erhalten wir schneller Lösungen, wenn wir nach 2% der durchschnittlichen Versuche bei Tiefe 78 abbrechen. Nämlich durchnittlich 5 mal so viele bei vorgegebener Suchzeit. Diese Methode lässt sich auf andere Suchtiefen übertragen.
Beim 4-Farben Problem haben wir zunächst nur Versuchszahlen bei Tiefe <= 254. Trotzdem können wir versuchen, die Ergebnisse aus dem 3-Farben Problem (mit vollständigen Lösungen) zu übertragen um abzuschätzen, wann wir eine Suche abbrechen sollten.
3) Variation der Suche
Das Abbrechen funktioniert natürlich nur, wenn jede Suche jedesmal anders verläuft. Man kann z.B. die Reihenfolge der Steine ändern.
Arbeitet man mit einer vorgegebenen 3-Farben Lösung die man erweitert, so sollte man darauf achten viele 3-er Lösungen mit verschiedenen
Aussenkanten zu verwenden (ich selbst hatte ca. 16000 3er Lösungen generiert).
4) Lösung
Inzwischen habe ich eine (potentielle) Lösung gefunden, vielleicht kann jemand anderes versuchen, sie zu verifizieren?
Die 256 Teile sind folgendermassen numeriert (beginnend bei 0, die Farben sind von 0-3 kodiert):
0: [0, 0, 0, 0]; 1: [1, 0, 0, 0]; 2: [2, 0, 0, 0]; 3: [3, 0, 0, 0]; 4: [0, 1, 0, 0]; 5: [1, 1, 0, 0]; 6: [2, 1, 0, 0]; 7: [3, 1, 0, 0]; 8: [0, 2, 0, 0]; 9: [1, 2, 0, 0]; 10: [2, 2, 0, 0]; 11: [3, 2, 0, 0]; 12: [0, 3, 0, 0]; 13: [1, 3, 0, 0]; 14: [2, 3, 0, 0]; 15: [3, 3, 0, 0]; 16: [0, 0, 1, 0]; 17: [1, 0, 1, 0]; 18: [2, 0, 1, 0]; 19: [3, 0, 1, 0]; 20: [0, 1, 1, 0]; 21: [1, 1, 1, 0]; 22: [2, 1, 1, 0]; 23: [3, 1, 1, 0]; 24: [0, 2, 1, 0]; 25: [1, 2, 1, 0]; 26: [2, 2, 1, 0]; 27: [3, 2, 1, 0]; 28: [0, 3, 1, 0]; 29: [1, 3, 1, 0]; 30: [2, 3, 1, 0]; 31: [3, 3, 1, 0]; 32: [0, 0, 2, 0]; 33: [1, 0, 2, 0]; 34: [2, 0, 2, 0]; 35: [3, 0, 2, 0]; 36: [0, 1, 2, 0]; 37: [1, 1, 2, 0]; 38: [2, 1, 2, 0]; 39: [3, 1, 2, 0]; 40: [0, 2, 2, 0]; 41: [1, 2, 2, 0]; 42: [2, 2, 2, 0]; 43: [3, 2, 2, 0]; 44: [0, 3, 2, 0]; 45: [1, 3, 2, 0]; 46: [2, 3, 2, 0]; 47: [3, 3, 2, 0]; 48: [0, 0, 3, 0]; 49: [1, 0, 3, 0]; 50: [2, 0, 3, 0]; 51: [3, 0, 3, 0]; 52: [0, 1, 3, 0]; 53: [1, 1, 3, 0]; 54: [2, 1, 3, 0]; 55: [3, 1, 3, 0]; 56: [0, 2, 3, 0]; 57: [1, 2, 3, 0]; 58: [2, 2, 3, 0]; 59: [3, 2, 3, 0]; 60: [0, 3, 3, 0]; 61: [1, 3, 3, 0]; 62: [2, 3, 3, 0]; 63: [3, 3, 3, 0]; 64: [0, 0, 0, 1]; 65: [1, 0, 0, 1]; 66: [2, 0, 0, 1]; 67: [3, 0, 0, 1]; 68: [0, 1, 0, 1]; 69: [1, 1, 0, 1]; 70: [2, 1, 0, 1]; 71: [3, 1, 0, 1]; 72: [0, 2, 0, 1]; 73: [1, 2, 0, 1]; 74: [2, 2, 0, 1]; 75: [3, 2, 0, 1]; 76: [0, 3, 0, 1]; 77: [1, 3, 0, 1]; 78: [2, 3, 0, 1]; 79: [3, 3, 0, 1]; 80: [0, 0, 1, 1]; 81: [1, 0, 1, 1]; 82: [2, 0, 1, 1]; 83: [3, 0, 1, 1]; 84: [0, 1, 1, 1]; 85: [1, 1, 1, 1]; 86: [2, 1, 1, 1]; 87: [3, 1, 1, 1]; 88: [0, 2, 1, 1]; 89: [1, 2, 1, 1]; 90: [2, 2, 1, 1]; 91: [3, 2, 1, 1]; 92: [0, 3, 1, 1]; 93: [1, 3, 1, 1]; 94: [2, 3, 1, 1]; 95: [3, 3, 1, 1]; 96: [0, 0, 2, 1]; 97: [1, 0, 2, 1]; 98: [2, 0, 2, 1]; 99: [3, 0, 2, 1]; 100: [0, 1, 2, 1]; 101: [1, 1, 2, 1]; 102: [2, 1, 2, 1]; 103: [3, 1, 2, 1]; 104: [0, 2, 2, 1]; 105: [1, 2, 2, 1]; 106: [2, 2, 2, 1]; 107: [3, 2, 2, 1]; 108: [0, 3, 2, 1]; 109: [1, 3, 2, 1]; 110: [2, 3, 2, 1]; 111: [3, 3, 2, 1]; 112: [0, 0, 3, 1]; 113: [1, 0, 3, 1]; 114: [2, 0, 3, 1]; 115: [3, 0, 3, 1]; 116: [0, 1, 3, 1]; 117: [1, 1, 3, 1]; 118: [2, 1, 3, 1]; 119: [3, 1, 3, 1]; 120: [0, 2, 3, 1]; 121: [1, 2, 3, 1]; 122: [2, 2, 3, 1]; 123: [3, 2, 3, 1]; 124: [0, 3, 3, 1]; 125: [1, 3, 3, 1]; 126: [2, 3, 3, 1]; 127: [3, 3, 3, 1]; 128: [0, 0, 0, 2]; 129: [1, 0, 0, 2]; 130: [2, 0, 0, 2]; 131: [3, 0, 0, 2]; 132: [0, 1, 0, 2]; 133: [1, 1, 0, 2]; 134: [2, 1, 0, 2]; 135: [3, 1, 0, 2]; 136: [0, 2, 0, 2]; 137: [1, 2, 0, 2]; 138: [2, 2, 0, 2]; 139: [3, 2, 0, 2]; 140: [0, 3, 0, 2]; 141: [1, 3, 0, 2]; 142: [2, 3, 0, 2]; 143: [3, 3, 0, 2]; 144: [0, 0, 1, 2]; 145: [1, 0, 1, 2]; 146: [2, 0, 1, 2]; 147: [3, 0, 1, 2]; 148: [0, 1, 1, 2]; 149: [1, 1, 1, 2]; 150: [2, 1, 1, 2]; 151: [3, 1, 1, 2]; 152: [0, 2, 1, 2]; 153: [1, 2, 1, 2]; 154: [2, 2, 1, 2]; 155: [3, 2, 1, 2]; 156: [0, 3, 1, 2]; 157: [1, 3, 1, 2]; 158: [2, 3, 1, 2]; 159: [3, 3, 1, 2]; 160: [0, 0, 2, 2]; 161: [1, 0, 2, 2]; 162: [2, 0, 2, 2]; 163: [3, 0, 2, 2]; 164: [0, 1, 2, 2]; 165: [1, 1, 2, 2]; 166: [2, 1, 2, 2]; 167: [3, 1, 2, 2]; 168: [0, 2, 2, 2]; 169: [1, 2, 2, 2]; 170: [2, 2, 2, 2]; 171: [3, 2, 2, 2]; 172: [0, 3, 2, 2]; 173: [1, 3, 2, 2]; 174: [2, 3, 2, 2]; 175: [3, 3, 2, 2]; 176: [0, 0, 3, 2]; 177: [1, 0, 3, 2]; 178: [2, 0, 3, 2]; 179: [3, 0, 3, 2]; 180: [0, 1, 3, 2]; 181: [1, 1, 3, 2]; 182: [2, 1, 3, 2]; 183: [3, 1, 3, 2]; 184: [0, 2, 3, 2]; 185: [1, 2, 3, 2]; 186: [2, 2, 3, 2]; 187: [3, 2, 3, 2]; 188: [0, 3, 3, 2]; 189: [1, 3, 3, 2]; 190: [2, 3, 3, 2]; 191: [3, 3, 3, 2]; 192: [0, 0, 0, 3]; 193: [1, 0, 0, 3]; 194: [2, 0, 0, 3]; 195: [3, 0, 0, 3]; 196: [0, 1, 0, 3]; 197: [1, 1, 0, 3]; 198: [2, 1, 0, 3]; 199: [3, 1, 0, 3]; 200: [0, 2, 0, 3]; 201: [1, 2, 0, 3]; 202: [2, 2, 0, 3]; 203: [3, 2, 0, 3]; 204: [0, 3, 0, 3]; 205: [1, 3, 0, 3]; 206: [2, 3, 0, 3]; 207: [3, 3, 0, 3]; 208: [0, 0, 1, 3]; 209: [1, 0, 1, 3]; 210: [2, 0, 1, 3]; 211: [3, 0, 1, 3]; 212: [0, 1, 1, 3]; 213: [1, 1, 1, 3]; 214: [2, 1, 1, 3]; 215: [3, 1, 1, 3]; 216: [0, 2, 1, 3]; 217: [1, 2, 1, 3]; 218: [2, 2, 1, 3]; 219: [3, 2, 1, 3]; 220: [0, 3, 1, 3]; 221: [1, 3, 1, 3]; 222: [2, 3, 1, 3]; 223: [3, 3, 1, 3]; 224: [0, 0, 2, 3]; 225: [1, 0, 2, 3]; 226: [2, 0, 2, 3]; 227: [3, 0, 2, 3]; 228: [0, 1, 2, 3]; 229: [1, 1, 2, 3]; 230: [2, 1, 2, 3]; 231: [3, 1, 2, 3]; 232: [0, 2, 2, 3]; 233: [1, 2, 2, 3]; 234: [2, 2, 2, 3]; 235: [3, 2, 2, 3]; 236: [0, 3, 2, 3]; 237: [1, 3, 2, 3]; 238: [2, 3, 2, 3]; 239: [3, 3, 2, 3]; 240: [0, 0, 3, 3]; 241: [1, 0, 3, 3]; 242: [2, 0, 3, 3]; 243: [3, 0, 3, 3]; 244: [0, 1, 3, 3]; 245: [1, 1, 3, 3]; 246: [2, 1, 3, 3]; 247: [3, 1, 3, 3]; 248: [0, 2, 3, 3]; 249: [1, 2, 3, 3]; 250: [2, 2, 3, 3]; 251: [3, 2, 3, 3]; 252: [0, 3, 3, 3]; 253: [1, 3, 3, 3]; 254: [2, 3, 3, 3]; 255: [3, 3, 3, 3];
Dann ist eine (potentielle) Lösung - p:t bedeutet Teil t ist an Position p, wobei die Positionen Reihe für Reihe durchnumeriert sind:
|0:4|1:17|2:64|3:16|4:17|5:37|6:137|7:38|8:149|9:77|10:47|11:163|12:140|13:35|14:184|15:218|16:80|17:84|18:81|19:17|20:33|21:34|22:18|23:72|24:6|25:49|26:216|27:122|28:210|29:120|30:187|31:135|32:5|33:21|34:85|35:65|36:8|37:34|38:164|39:161|40:128|41:12|42:55|43:205|44:23|45:93|46:75|47:50|48:0|49:20|50:69|51:1|52:32|53:168|54:170|55:138|56:2|57:48|58:252|59:243|60:244|61:245|62:193|63:60|64:160|65:148|66:97|67:144|68:88|69:90|70:106|71:146|72:96|73:156|74:79|75:31|76:111|77:143|78:3|79:44|80:154|81:102|82:169|83:166|84:165|85:133|86:41|87:150|88:105|89:182|90:241|91:196|92:57|93:226|94:176|95:232|96:86|97:73|98:26|99:74|100:42|101:130|102:40|103:134|104:25|105:94|106:127|107:211|108:124|109:203|110:14|111:59|112:101|113:129|114:36|115:145|116:104|117:162|118:152|119:98|120:132|121:53|122:237|123:183|124:119|125:115|126:240|127:236|128:102|129:66|130:24|131:70|132:9|133:10|134:22|135:89|136:82|137:108|138:171|139:190|140:215|141:109|142:175|143:155|144:246|145:209|146:100|147:177|148:208|149:112|150:212|151:117|152:229|153:185|154:234|155:174|156:151|157:121|158:250|159:214|160:95|161:119|162:233|163:158|164:71|165:45|166:167|167:189|168:235|169:142|170:43|171:186|172:198|173:61|174:255|175:231|176:197|177:29|178:91|179:118|180:225|181:34|182:58|183:222|184:107|185:178|186:200|187:30|188:83|189:76|190:15|191:27|192:51|193:228|194:181|195:253|196:251|197:194|198:28|199:103|200:102|201:110|202:147|203:116|204:213|205:113|206:224|207:180|208:51|209:11|210:46|211:191|212:239|213:131|214:52|215:201|216:54|217:249|218:230|219:141|220:39|221:173|222:187|223:206|224:179|225:192|226:56|227:254|228:219|229:114|230:220|231:99|232:188|233:223|234:123|235:242|236:248|237:202|238:62|239:195|240:126|241:227|242:172|243:159|244:87|245:125|246:247|247:217|248:78|249:7|250:13|251:63|252:207|253:19|254:92|255:67
Hallo Dietmar,
ich kann Deine Lösung bislang nur teilweise bestätigen: Die 256 Bauteilesind zumindest schon einmal eindeutig (aber das war ja auch der einfache Teil).
Die Lösung als solche kann ich leider bislang noch nicht bestätigen, da mir nicht ganz klar ist, wie Du die Teile anordnen möchtest.
Sehe ich das Richtig: Das Spielfeld sieht wie folgt aus:
0 | 1 | 2 | 3 ...
16 | 17 | 18 | 19 ...
32 | 33 | 34 | 35 ...
Wenn ich jetzt das erste Teil legen möchte, sieht das nach Deiner Lösung wie folgt aus:
Teil: 4: [0, 1, 0, 0]
Position: |0:4|
Die obere linke Ecke müßte daher wie folgt aussehen:
0 1
0 0
Daran schließt dann das nächste Teil an:
Teil: 17: [1, 0, 1, 0]
Position: 1:17
0 1 | 1 0
0 0 | 1 0
Schon beim 2. Teil klappt's also nicht. Oder verwendest Du eine andere Anordnung?
Gruß
Thomas
\\//_ Build long and ℘rosper!
Hallo Dietmar, hallo Thomas,
ich habe noch etwas mehr Probleme beim Nachvollziehen:
Die Liste hat 1:17 und etwas später 4:17 ...
Das würde bedeuten, dass das Teil 17 (mindestens) zwei Mal vorkäme.
Hmm, Ingo.
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Das ist richtig, es gibt ein Problem mit der Lösung. Teil 17 wird zweimal angezeigt. Da gibt es noch ein Problem mit dem Verfahren. Beim 2-Farben Problem bekomme ich auch 800 Lösungen, also hat es mit den Verbesserungen zu tun. Das vorher berechnete 9x9er, das ich als Basis verwende, wurde anscheinend falsch eingetragen. Ein 256er sollte aber trotzdem möglich sein, werde den Fehler beheben und es dann weiter versuchen.
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
Vielen Dank für die Unterstützung. Wie auch Ingo schon bemerkt hat, gab es noch einen Bug der jetzt hoffentlich gefixed ist. Das nächste Mal gibt es noch eine Ausgabe in der Form (hier für das 9x9er):
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
da sieht man schneller was Sache ist. Die Performance der Suche scheint unverändert - alle paar Minuten einen 253er. Morgen oder ünermorgen haben wir dann hoffentlich einen korrekten 256er.
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)
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.
drdwo hat geschrieben:
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:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Liebär Ingo!
Gehört das nich so:
Lieber Mich.a,
Eisbär hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
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.
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
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)
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:
drdwo hat geschrieben:
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
Hallo Dietmar,
drdwo hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
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
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
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)
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.
Hallo Dietmar,
danke für Deine interessanten Erläuterungen und Einordnungen
zu den verschiedenen Puzzles.
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Liebär Ingo!
Lieb.er Eisbär!
Eisbär hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Liebär Ingo!
Klötern is, wenn Legos fallen.
Klöterig is, wenn mich.a ein Wortspiel einfällt. Oder eine schiefe Metapher. Es soll ja wirklich schon mal vorgekommen sein, obwohl sich niemand daran erinnern kann, daß ich mal gewußt habe, wovon ich so dahertäzele.
Mich.a dünkte, Mathematiker und -Innen, inkl. Lehrämtler und -Innen, nebützten n für "irgendeine Zahl*", nun nehmen sie aber k. Kein Wunder, daß ich tüdelig werd'.
Soso, Originohllegoländer lügen nicht. Warn das nicht die Minoer?
Kretische Grüße
M.a
*Von weiteren Delfinischohnen, wie ganze, natürliche, indiskrete usw. ist abzusehen.
Eisbär hat geschrieben:
LLL!
Man soll ja vor Erkenntnisgewinnen nicht immer zurückschrecken.
Daher habe ich mal bei wikipedia nach indiskreten Zahlen gesucht. Und ein Manko feststellen müssen.
Gefunden habe ich etwas zu "Diskreter Mathematik" und zwar:
WolframBernhardt
29.07.2016, 23:40
Als Antwort auf den Beitrag von drdwo
Editiert von
WolframBernhardt
29.07.2016, 23:41
Hallo!
Ich hatte mich mit dem ursprünglichen Rätsel 2010 intensiv befasst und schaue mir nun auch das größere 256er-Problem an.
Als erstes habe ich ein Art Regelfrage, die sich auf die Beschaffenheit der Klötze bezieht.
Im ursprünglich Rätsel gab es Steine, die von der Farbgebung her identisch waren (z.b. eine Ecke rot, die anderen Ecken blau), aber durch Asymmetrie, die die weissen Trennbalken hinzufügen, waren es doch andere Steine. Dadurch wurde es nötig, sinnvoll und interessant, mit Drehungen zu arbeiten. Steine, die von den Eckfarben her passen würden, passen ggf. nicht, weil ein breites Farbstück auf ein schmales trifft.
Wurden das bei den Lösungen zum 256er-Rätsel berücksichtigt? Wurden die weissen Balken in den Lösung mitberechnet und nur in der Darstellung weggelassen?
Mein Eindruck ist, dass durch Durchzählen alle möglichen Steine erzeugt wurden. Da es keine Asymmetrie zu geben scheint, sieht es so aus als ob die Lösungen gleiche Steine enthalten, also Steine, die durch Drehung genauwie wie die anderen Steinen werden können.
In dieser Lösung z.B. gibt es gleich in der ersten Zeile zwei Steine (ich habe sie mit Pipes umgeben), die - wenn man mit Drehung arbeitet - identisch sich. Eine Eins in einer Ecke, die anderen vier Ecken Nullen.
Wie seht Ihr das? Wenn man es ohne weissen Trennbalken Klotz (also symmetrisch) und mit Drehungen betrachtet, kommt man gar nicht auf 256 verschiedene Steine. Wenn man wirklich 256 verschiedene Steine betrachten will, muss man die weissen Trennbalken berücksichtigen und wahrscheinlich auch Drehungen miteinbeziehen, oder?
drdwo hat geschrieben:
Aus den obigen Diskussionen habe ich jetzt gelesen, dass eher davon ausgegangen wird, dass die Steine nicht gedreht werden sollen.
Das ist gut und erleichtert mir auch die "Arbeit" am 256er-Ding :-)
Halo Wolfram,
willkommen bei den 1000steinern!
WolframBernhardt hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)