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)

Eisbär
21.06.2016, 08:54

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

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.

[image]



ÜBärforderte Grüße
M.a



IngoAlthoefer
21.06.2016, 09:17

Als Antwort auf den Beitrag von Eisbär

Re: Puzzle mit 4x4 Teilen

Lieber Micha,

Eisbär hat geschrieben:

Ich fürchte, meine logischen Fähigkeiten sind unzureichend.

Geschenkt

Man soll also alle Teile zusammenlegen, nicht Domino spielen?
In welcher Façon soll das Zusammengelegte denn sein? Quadrat?

Genau. 4x4 beschreibt nicht nur die Anzahl, sondern auch die Form.

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.

Und gerade wegen Dir als Beute-Norweger hatte ich diese Farben gewählt.
Tipp: Weil es LEGO-Steine nicht nur in weiß, rot und blau gibt, kann man
ändern. Wenn Du z.B. rot durch gelb ersetzt, erinnert es höchsterns an
die schwedische Flagge.


Vorschlag für alle, die nicht ausgelastet sind:
Was passiert, wenn man das Puzzle auf 4 Farben (statt nur blau und rot) erweitert?
Wieviel verschiedene Teile hat man dann? Wer kann dazu eine Lösung angeben?


Viele Grüsse, Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


cimddwc
21.06.2016, 11:10

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

IngoAlthoefer hat geschrieben:

Vorschlag für alle, die nicht ausgelastet sind:
Was passiert, wenn man das Puzzle auf 4 Farben (statt nur blau und rot) erweitert?
Wieviel verschiedene Teile hat man dann?

Hallo,

naja, mit 2 Farben für 4 Teilfelder sind's obige 2^4=16, mit 4 Farben also 4^4=256. Aber bauen und anordnen dürfen das andere, die wirklich Zeit haben.

Grüße,
Andreas



IngoAlthoefer
21.06.2016, 11:51

Als Antwort auf den Beitrag von cimddwc

Re: Puzzle mit 4x4 Teilen

Hallo Andreas,

cimddwc hat geschrieben:


... naja, mit 2 Farben für 4 Teilfelder sind's obige 2^4=16,
mit 4 Farben also 4^4=256. Aber bauen und anordnen dürfen
das andere, die wirklich Zeit haben.

dann noch eine Aufgabe für die halbausgelasteten:
3 Farben; also 3 hoch 4 = 81 Teile,
anzuordnen im 9x9-Gitter.

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Kirk
21.06.2016, 15:46

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

Hallo Ingo,

ein Puzzle, wo 4 x 4 Teileso aneinander zu legen sind, dass alle Übergänge passen.
Es gibt mehr als 400 Lösungen.

wenn ich mich nicht schwer verrechnet habe, gibt es exakt 800 Lösungen. Da es sich um lauter verschiedene Puzzel-Teile handelt, habe ich nicht auf Symmetrien geprüft, weil es die nicht geben dürfte. Die Ausrichtung der Teile ist dabei natürlich fest, also das Feld mit nur 1 Noppe ist stets links oben.

3 Farben; also 3 hoch 4 = 81 Teile,
anzuordnen im 9x9-Gitter.

Bislang habe ich über 80 Lösungen gefunden, die Suche läuft aber noch.

Was passiert, wenn man das Puzzle auf 4 Farben (statt nur blau und rot) erweitert?
Wieviel verschiedene Teile hat man dann?

Nunja, bis hierher ist die Sache einfach: 4 Farben verteilt auf 4 Positionen ergibt 4^4 = 256 Puzzelteile (also eine 16x16-Grundfläche).

Wer kann dazu eine Lösung angeben?

Bislang leider Fehlanzeige. Im besten Fall konnte ich bis zu 77 Teile verbauen, aber dann ging's irgendwie nicht recht weiter. Auch hier läuft die Suche noch.

Gruß

Thomas


\\//_ Build long and ℘rosper!


IngoAlthoefer
21.06.2016, 19:13

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen

Hallo Thomas,

Kirk hat geschrieben:

Es gibt mehr als 400 Lösungen.

wenn ich mich nicht schwer verrechnet habe, gibt es exakt 800 Lösungen.

Stimmt genau!

3 Farben; also 3 hoch 4 = 81 Teile,
anzuordnen im 9x9-Gitter.

Bislang habe ich über 80 Lösungen gefunden, die Suche läuft aber noch.

Naiv hätte ich gedacht, deutlich mehr als 800 Lösungen.
Aber jetzt komme ich ins Zweifeln...

Wer kann zum 4-Farben-Puzzle eine Lösung angeben?

Bislang leider Fehlanzeige. Im besten Fall konnte ich bis zu 77 Teile verbauen,
aber dann ging's irgendwie nicht recht weiter. Auch hier läuft die Suche noch.

Hmm.
Wenn nicht alle 256 Teile einpassbar sind, wäre die Notaufgabe, soviele wie
möglich passend (und zusammenhängend) in einen 16x16-Rahmen zu setzen.

Halte mich bitte auf dem Laufenden.

Viele Grüsse, Ingo.


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

Re: Puzzle mit 4x4 Teilen

Hallo Ingo,

IngoAlthoefer hat geschrieben:

Kirk hat geschrieben:
exakt 800 Lösungen.

Stimmt genau!

Prima, das ist ja schonmal ein guter Anfang :-)

IngoAlthoefer hat geschrieben:
3 Farben [...] Naiv hätte ich gedacht, deutlich mehr als 800 Lösungen.

Ich habe leider einen recht altersschwachen Rechner, da notwendige Investitionen zu Gunsten meiner LEGO Leidenschaft immer zurück treten mußten. Mittlerweile habe ich schon über 130 Lösungen gefunden und die Suche läuft weiter. Da ich bei weitem nicht alle Kombinationen teste, sondern ähnlich wie ein Mensch Teil für Teil anfüge, führt jeder Fehlversuch dazu, daß gleich mal Millionen Kombinationen der noch übrigen Teile wegfallen, so daß ich gar nicht genau weiß, wie weit ich eigentlich bin.
Beim 2-Farb-Problem sah die Sache so aus:
2 Farben auf 4 Feldern => 2^4 = 16 Puzzelteile
Theoretisch mögliche Anordnungen (Du würdest wohl von Permutationen sprechen): 16! = 20.922.789.888.000 = 21 Billionen Möglichkeiten.
Tatsächlich habe ich davon aber nur etwa 40 Tausend geprüft - also quasi ein fünfhundert-millionstel
Ich werde meinen Rechner auf jeden Fall über Nacht weiter suchen lassen und morgen Abend ein Zwischenergebnis posten.

Wenn nicht alle 256 Teile einpassbar sind, wäre die Notaufgabe, soviele wie
möglich passend (und zusammenhängend) in einen 16x16-Rahmen zu setzen.

Rein gefühlsmäßig würde ich behaupten, daß sich für jedes dieser Puzzel eine (Trivial-)Lösung errechnen lassen müsste, wenn man binäre Muster anwendet, aber das ist wie gesagt nur eine kühne These.
Mittlerweile konnte ich schon etwas mehr als die Hälfte aller 4-Farb-Teile verbauen. Auch diese Suche werde ich über Nacht laufen lassen und ggf. so umbauen, daß mir die von Dir gewünschte Zwischenlösung angezeigt wird.

Gruß

Thomas


\\//_ Build long and ℘rosper!


Kirk
22.06.2016, 00:01

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

IngoAlthoefer hat geschrieben:

Naiv hätte ich gedacht, deutlich mehr als 800 Lösungen.
Aber jetzt komme ich ins Zweifeln...


Hallo Ingo,

ich kann Dich beruhigen: Deine Vermutung ist richtig! Ich habe gerade die Marke von 800 Lösungen (mittlerweile sogar schon 900 Lösungen) bei den dreifarbigen Teilen überschritten, nachdem ich ungefähr 2.3 Mrd. Züge durchprobiert habe. Ich bin schon selbst ganz gespannt, wo der Zähler morgen Abend stehen wird.

Beim Vier-Farb-Problem bin ich ebenfalls schon weiter und habe deutlich über 200 Teile (von 256) verbauen können, wobei ich dafür weit über 6 Mrd. Versuche gebraucht habe, aber eine vollständige Lösung war bislang leider noch nicht dabei.

Gruß

Thomas


\\//_ Build long and ℘rosper!


Kirk
22.06.2016, 06:59

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

IngoAlthoefer hat geschrieben:

Naiv hätte ich gedacht, deutlich mehr als 800 Lösungen.
Aber jetzt komme ich ins Zweifeln...


Kleiner Zwischenstand:
3 Farben: Bislang knapp 5000(!) gefundene Lösungen
4 Farben: Auch nach weit über 11 Mrd. Versuchen noch keine komplette Lösung gefunden. Die letzten ca. 70 Teile wollen einfach nicht zusammenpassen :-(


\\//_ Build long and ℘rosper!


IngoAlthoefer
22.06.2016, 12:21

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Thomas,

Kirk hat geschrieben:

...
Da ich bei weitem nicht alle Kombinationen teste, sondern
ähnlich wie ein Mensch Teil für Teil anfüge, führt jeder
Fehlversuch dazu, daß gleich mal Millionen Kombinationen
der noch übrigen Teile wegfallen ...

Du machst also eine Art "Branch and Bound".

Dazu eine Frage: In welcher Reihenfolge füllst Du die Felder
beim Durchprobieren auf?

Eine normale bei 4x4 wäre diese zeilenweise Nummerierung:

[image]



Etwas bessere Abschneideraten dürfte man aber bekommen,
wenn man folgende Reihung nutzt:

[image]



Die Zahlen unter den Gittern geben die nachbarbedingungen an, die in den einzelnen
Schritten zu erfüllen sind.

Für 4x4 kennst Du ja schon die Lösung, trotzdem wäre es für mich interessant zu
sehen, wie schnell die beiden Reihungen im Vergleich arbeiten.

*************************************
Für 9x9-Gitter wären die analogen Reihungen

[image]


und

[image]



In diesem Fall könnte die Reihenfolge schon wirklich einen Unterschied im Bereich
von Rechenstunden oder Grössenordnungen machen.

Viele Grüsse, Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Eisbär
22.06.2016, 12:54

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Liebär Ingo!

Hm.

Man nehme die Teile und lege sie zusammen, so daß herauskommt:

[image]



Daher frug ich nach dem Quadrat.

Es gibt mindestens eine Nationalflagge, die quadratisch ist.

Apropos: Ich hatte ja mal die Idee, weil ich zufällig mal einen schwarzen 2x4x1 auf einem roten auf einem güldenen hatte, alle Nationalflaggen aus Lego zu bauen. Das hört sich leichter an, als es ist, denn es gibt da einige, die nicht nur rechte Winkel haben. Käme dann auf Größe und Detailgenauigkeit an. Außerdem haben einige auch „komische“ Maße (Verhältnis der Seiten zueinander). Fast so wie die Legos.

Mich.a wundert es ja, daß man dieses Puzzle bärechnen muß: gibbs da nich ne fertige Formel für? Die Althoefersche Vermuthung? Und Du willst uns dazu bringen, sie zu beweisen.

Verpuzzelte Grüße
M.a



IngoAlthoefer
22.06.2016, 13:35

Als Antwort auf den Beitrag von Eisbär

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Mich.a,

Eisbär hat geschrieben:

...
Mich.a wundert es ja, daß man dieses Puzzle bärechnen muß:
gibbs da nich ne fertige Formel für?

Die gibt es beweisbar nicht.

Puzzles sind für die Ewigkeit. Siehe dazu auch:
https://de.wikipedia.org/wiki/Eternity-Puzzle

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Bricoon
22.06.2016, 13:53

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen

IngoAlthoefer hat geschrieben:


[image]


Links eine Teillösung aus sieben Elementen. Am Ende müssen an allen Übergangsstellen
alle Farben zueinander passen.

Das ist gar keine Teillösung
Um auf eine 4x4 Lösung zu kommen, müssen wir am rechten Rand entweder oben oder unten einen Stein ansetzen. Es passt jedoch kein verbleibender Stein. Es folgt: die sieben Elemente in ihrer gezeigten Zusammenstellung ergeben keine Teillösung.

Ansonsten hast du mich erfolgreich von der Arbeit abgehalten . Ich mag solche Puzzles.

Grüße
Tobi Bricoon



-jc-
22.06.2016, 13:56

Als Antwort auf den Beitrag von Bricoon

Editiert von
-jc-
22.06.2016, 13:56

Re: Puzzle mit 4x4 Teilen

Bricoon hat geschrieben:

Um auf eine 4x4 Lösung zu kommen, müssen wir am rechten Rand entweder oben oder unten einen Stein ansetzen. Es passt jedoch kein verbleibender Stein.

doch, der "lose" Stein ganz unten rechts passt unten rechts dran ;)

Gruß
Jürgen



Eisbär
22.06.2016, 14:10

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



Kirk
22.06.2016, 22:07

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Ingo,

IngoAlthoefer hat geschrieben:

Du machst also eine Art "Branch and Bound".

Jein. Von Branch-and-Bound spricht man laut Wikipedia offenbar bei Problemen, bei denen sich eine beliebige Lösung recht schnell ergibt, aber eigentlich die beste Lösung gesucht wird. Ich würde das Verfahren viel Banaler als "Trial and Error" bezeichnen oder (um im IT-Jargon zu bleiben) "Brute-Force".


IngoAlthoefer hat geschrieben:
In welcher Reihenfolge füllst Du die Felder beim Durchprobieren auf?

Wie von Dir richtig vermutet, teste ich von links nach rechts und danach von oben nach unten.

IngoAlthoefer hat geschrieben:
Etwas bessere Abschneideraten dürfte man aber bekommen, wenn man folgende Reihung nutzt: (Diagonal)

Keine gute Idee.
Es fängt mal damit an, daß ich mein Programm so gestaltet habe, daß sich anhand der vorgegebenen Farben automatisch die Größe des Spielbretts ergibt. Um das nächste Feld zu finden, gibt es drei einefach Regeln:
1.) Gehe ein Feld nach rechts.
2.) Wenn dabei der rechte Spielfeldrand überschritten wird, gehe eine Zeile runter und auf Spalte "1".
3.) Wenn auch der untere Spielfeldrand überschritten wird, wurden logischerweise alle Teile verbaut. Demnach wurde eine Lösung gefunden.
Für Deinen Diagonalen Ansatz müßte man vermutlich die Reihenfolge der Felder vorberechnen, denn dieses komplizierte Muster läßt sich nicht sinnvoll "in Echtzeit" berechnen. Hätte ich tatsächlich die Muße, das 2-Farben-Programm entsprechend umzubauen, würde ich die Reihenfolge manuell vorgeben, denn einen Algorithmus zu definieren, der dieses Muster auf einem 4x4-Brett erzeugt, würde wesentlich länger dauern, als die 16 Koordinaten von Hand zusammen zu tippen.

IngoAlthoefer hat geschrieben:
wie schnell die beiden Reihungen im Vergleich arbeiten.

Die Frage ist leicht zu beantworten, auch ohne daß ich es empirisch teste:
Dein Ansatz ist ungefähr gleich schnell bis deutlich langsamer(!). Es sei denn... - aber dazu später.

Nehmen wir an, ich ich würde lediglich mein Verfahren (links nach rechts) durch Dein Verfahren (diagonal) ersetzen, dann dürfte sich an der Laufzeit nicht viel ändern - vielleicht wäre das Programm sogar im Promille-Bereich schneller, aber das würde kaum ins Gewicht fallen.

Nun ist aber Deine Argumentation, daß man durch die Diagonalen Rechenschritte einsparen könnte: Das stimmt so leider nicht, denn ein Puzzel-Teil paßt immer dann auf's freie Feld, wenn oben und links entweder die Farben überein stimmen oder aber das angrenzende Feld leer ist. Insofern würde sich daraus keine einzige Einsparung ergeben, weil ich ja doch immer beide Bedingungen prüfen muß.

Man könnte jetzt auf die Idee kommen, noch eine Fallunterscheidung einzubauen, bei welchen Feldern man überhaupt welche Nachbarn prüfen muß, aber von den 16 Feldern haben nur die oberen und linken Seiten jeweils einen Nachbarn (unten und rechts braucht nicht geprüft zu werden, denn diese Felder sind ja jeweils noch leer). Das würde aber bedeuten, daß man bei 7 von 16 Feldern (=44%) minimal Rechenzeit sparen könnte, aber dafür bei 100% aller Fälle zusätzliche Prüfungen durchführen müssen. Unterm Strich würde sich eine massive Verschlechterung ergeben.

Wie oben erwähnt, könnte Deine Idee unter gewissen Rahmenbedingungen etwas bringen: Es gibt Programmiersprachen (wie z.B. "C"), in denen man den Anfangspunkt einer Programmfunktion in einer Variable hinterlegen kann, so daß man quasi im Vorfeld für alle 16 Felder vordefinieren kann, welche Tests ausgeführt werden sollen. Man könnte also bei 44% der Tests jeweils vielleicht 5-10% Zeit sparen - im Optimalfall also rund 5%. Aus dem Bauch heraus glaube ich aber nicht, daß es sich tatsächlich so stark bemerkbar macht, denn Du möchtest ja die "einfachen" Tests am Anfang machen. Tatsächlich ist es aber so, daß Anfang der Suche jeder Baustein vergleichsweise selten gewechselt wird. Je weiter man nach hinten kommt, desto öfter müssen die Tests ausgeführt werden. Es ist also eher vorteilhaft, auch am Ende noch ein paar dieser "einfachen" Tests übrig zu haben - und das trifft eher auf meine lineare Methode zu.

Unterm Strich müßte man viel Arbeit für einen vergleichsweise geringen Nutzen investieren. Viel effektiver wäre es wohl, wenn ich eine andere Sprache verwenden würde, denn ich bin Fan von PERL, das sich wesentlich besser für kaufmännische Anwendungen eignet und nur bedingt für mathematische Spielereien. Auch eine modernere Hardware anstelle meiner Antiquität würde wohl einiges bringen.

Gruß

Thomas

PS:
3 Farben: Bislang über 9500 gefundene Lösungen nach 9.8 Mrd. Zügen
4 Farben: Nach über 22 Mrd. Zügen noch immer keine Lösung in Sicht. Die Suche dümpelt nach wie vor bei rund 200 verbauten Teilen vor sich hin.


\\//_ Build long and ℘rosper!


Bricoon
22.06.2016, 23:25

Als Antwort auf den Beitrag von -jc-

Re: Puzzle mit 4x4 Teilen

-jc- hat geschrieben:

Bricoon hat geschrieben:
Um auf eine 4x4 Lösung zu kommen, müssen wir am rechten Rand entweder oben oder unten einen Stein ansetzen. Es passt jedoch kein verbleibender Stein.

doch, der "lose" Stein ganz unten rechts passt unten rechts dran ;)

Gruß
Jürgen


Ich bin davon ausgegangen, dass der farbige 1x1 Stein immer links oben sein muss. Dann passt er nämlich nicht.

Gruß
Tobi Bricoon



Kirk
23.06.2016, 01:16

Als Antwort auf den Beitrag von Bricoon

Re: Puzzle mit 4x4 Teilen

Bricoon hat geschrieben:

Ich bin davon ausgegangen, dass der farbige 1x1 Stein immer links oben sein muss. Dann passt er nämlich nicht.


Hallo Tobi,

stimmt, die Ausrichtung der weißen Kreuze muß bei allen Steinen identisch sein, denn sonst paßt es nicht.
Erst nachdem ich Dein ursprüngliches Posting mehrfach durchgelesen habe, ist mir aufgegangen, was genau Deine Frage ist, denn passende Steine gäbe es noch reichlich, aber Du hast Recht, daß es mit den verbliebenen Steinen unmöglich ist, das Gebilde auf eine Seitenlänge von 4 Teilen zu erweitern. Ich glaube, Du legst das Wort "Teillösung" zu eng aus. Ingo wollte lediglich zeigen, wie die Steine zusammen gelegt werden sollen. Er wollte damit nicht ausdrücken, daß man diese Anordnung tatsächlich als Grundlage für eine funktionierende Lösung hernehmen kann.

Gruß

Thomas

PS: So könnte eine gültige Lösung aussehen - noch 799 weitere Lösungen gilt es zu entdecken, wie Ingo und ich übereinstimmend ermittelt haben.

[image]


\\//_ Build long and ℘rosper!


-jc-
23.06.2016, 14:16

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen

Hallo,

da sich jedes Bild invertieren lässt, gibt es so gesehen "nur" 400 Lösungen
Also fehlen noch 398 *g*

Gruß
Jürgen



cimddwc
23.06.2016, 14:56

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



Kirk
23.06.2016, 20:57

Als Antwort auf den Beitrag von cimddwc

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Andreas,

cimddwc hat geschrieben:

Und das ganze schön optimiert in x86-Assembler. Die 2-Farb-Variante [...] findet die 800 Lösungen nach ca. 80.000 Versuchen in ca. 2 Millisekunden.

wow, das ist mal eine Ansage! Mein PERL-Programm hat für die 800 Lösungen immerhin knapp 2 Minuten gerechnet (wobei mir bewußt ist, daß meine Sprach-Wahl für derlei Programme absolut ungeeignet ist). Erstaunlicherweise habe ich die 800ste Lösung nach "nur" 45.000 Zügen gefunden, aber das kann auch Glück gewesen sein, denn je nachdem, in welcher Reihenfolge man insbesondere die ersten Steine durchprobiert, kommt man früher oder später zu dem Ergebnis. Auf jeden Fall "Hut ab" für Dein Programm!

cimddwc hat geschrieben:
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...

Hm... gefühlt würde ich sagen, daß Deine Quote um den Faktor 10 zu hoch liegt.
Du findest im Schnitt alle 100 Mrd/560.000 = 178.571 Züge eine Lösung.
Ich habe bislang "erst" 21 Mrd. Züge durchgespielt, aber auch erst 13.000 Lösungen gefunden - macht also eine Lösung alle 1.615.384 Züge.

cimddwc hat geschrieben:
Das 4-Farben-Programm läuft noch nicht so lange, das hat nach 7,5 Sekunden schon 246 Steine nach 350 Mio. Versuchen verbaut

Es beruhigt mich schonmal, daß es nicht nur mir so geht, daß trotz intensiver Suche kein Ergebnis zu Stande kommt.
Ich habe gestern noch eine 2. Instanz meiner 4-Farb-Suche gestartet, die auch Teil-Ergebnisse speichert. Ich habe immerhin 6.642.411.556 Züge gebraucht, um nur 237 Teile zu verbauen. Entweder hast Du ein sehr glückliches Händchen bei der Reihenfolge der Teile, oder aber Du hast doch noch einen Denkfehler im Programm, da ich knapp 20x so viele Züge brauchte, um deutlich weniger Steine zu verbauen.

Ich bin schon sehr gespannt, wann Du die erste Lösung findest! Laß uns beide die Daumen drücken, daß Ingo nicht noch mit einem Beweis um die Ecke kommt, daß das Problem unlösbar ist...

Gruß

Thomas


\\//_ Build long and ℘rosper!


cimddwc
23.06.2016, 22:11

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



cimddwc
23.06.2016, 22:33

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



Kirk
23.06.2016, 23:09

Als Antwort auf den Beitrag von cimddwc

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

cimddwc hat geschrieben:

Der Zähler wird erhöht, wenn in einem Feld n kein Stein mehr möglich ist


Aha, Du zählst also eher nur die Sackgassen. Dann ist es kein Wunder, wenn unsere Zählungen deutlich von einander abweichen, denn ich zähle die "Züge" (bin halt ein LEGO Eisenbahner ), wobei ein Zug jeder Versuch ist, einen Stein einzupassen. Ich zähle somit jeden Stein, den ich in die Hand nehme und erhöhe den Zähler, noch bevor ich prüfe, ob der Stein dort überhaupt hin paßt.


\\//_ Build long and ℘rosper!


Kirk
24.06.2016, 21:39

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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!


cimddwc
24.06.2016, 23:26

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



IngoAlthoefer
04.07.2016, 10:36

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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)


drdwo
04.07.2016, 16:25

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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



Kirk
04.07.2016, 17:32

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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!


IngoAlthoefer
04.07.2016, 18:12

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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)


drdwo
04.07.2016, 18:51

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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.



Kirk
04.07.2016, 19:47

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

IngoAlthoefer hat geschrieben:

Die Liste hat 1:17 und etwas später 4:17 ...


Ups... das hatte ich bei meiner Prüfung ganz übersehen. Tatsächlich kommt das Teil 17 sogar 3x vor (genau so wie die Teile 34 und 102), wohingegen diverse andere Teile fehlen. Ich habe dies jetzt bei meiner Gegenprobe berücksichtigt und bin schon gespannt, wann Dietmars Computer die nächste Lösung ausspuckt.


\\//_ Build long and ℘rosper!


drdwo
04.07.2016, 22:41

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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.



IngoAlthoefer
05.07.2016, 08:47

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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.



cimddwc
06.07.2016, 10:50

Als Antwort auf den Beitrag von drdwo

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

drdwo hat geschrieben:

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.

1.76e12. Wenn auch - siehe früheres Posting - einige zu viel gezählt worden sein dürften.

Grüße,
Andreas



Eisbär
06.07.2016, 11:58

Als Antwort auf den Beitrag von IngoAlthoefer

Farbfrage

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

[image]

in den Legogrundfarbe, aber die Anzahl stimmte mit der in der Frage nicht übärein. Gelbrotblauweißschwarz. Daher habe ich keine Antwort.

Avantgarde-Grüße
M.a



IngoAlthoefer
06.07.2016, 12:07

Als Antwort auf den Beitrag von drdwo

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

Hallo Dietmar,

drdwo hat geschrieben:

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

Ich extrapoliere mal: jedes Mal, wenn der Wert um 1 ansteigt,
geht die Anzahl gefundener um den Faktor 10 runter: 300 -> 30 -> 3
Also solltest Du bisher 0,3 256er gefunden haben (Hinweis für mich.a:
das ist angewandte diskrete Optimierung; nix mit ausgebrannten Halbbussen :-).
Also sollten ungefähr alle 3 Tage ein 256er dabei sein, wenn
das mit dem Faktor 10 allgemein gilt. (Aber jetzt bitte nicht spekulieren, ob
sich alle 30 Tage ein 257er findet ...)

Komisch ist, das die drei 255er alle auf einem (von 5) Rechnern
gefunden wurden. Die Wahrscheinlichkeit dafür ist glaube ich relativ gering.

Ist aber noch nicht statistisch signifikant. Der erste Treffer ist zufällig
auf diesem Rechner. Dann ist die W-keit für die beiden folgenden 1/25 = 4 %.

Deshalb vermutete ich zunächst, das ich auf diesem Rechner versehentlich
irgendetwas anders gemacht habe - habe aber nichts gefunden.

Vielleicht kannst Du ja "trotzdem" probehalber den Code dieses Rechners
auf einen der vier anderen übertragen. Oder hat der Rechner vielleicht
ein anderes Verfahren, den Pseudozufall zu initialisieren?

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Eisbär
06.07.2016, 12:47

Als Antwort auf den Beitrag von IngoAlthoefer

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

Liebär Ingo!

Also solltest Du bisher 0,3 256er gefunden haben (Hinweis für mich.a:
das ist angewandte diskrete Optimierung; nix mit ausgebrannten Halbbussen :-).


Eher dreiviertel, denn 0,3 von 256 sind: dreimal 250 = 750 plus dreimal 6 = 18 macht 768 durch zehn macht 76,8. FehlerABSchätzung: 70 mal drei sind 210, 80 mal drei sind 320, liegt so passend dazwischen, zufrieden.

Wo aber bleibt der Omnibus?

Und was ist unanwendbäre indiskrete Malifizierung?

Stimme aus dem OFF: Das is, wenn's kaputt is und in's Auge fällt.



Aufdringliche Grüße
M.a



IngoAlthoefer
06.07.2016, 12:51

Als Antwort auf den Beitrag von Eisbär

LEGondrian

Lieber mich.a,

Eisbär hat geschrieben:

Mondrian ist gut, aber war der damals
auch in Billund schon weltbärühmt?

Die hatten zwar nur einen Bahnhof und drei Strassen,
aber Mondrian (gestorben 1944) kannte und schätzte
man überall. Warum ich das "1944" so gut weiss? Urheberrecht
schützt ja für 70 Jahre nach dem Tod des Künstlers.
Und 70 Jahre plus 1 Tag nach Mondrians Tod eröffnete in
Hamburg eine grosse Mondrian-Ausstellung. (So etwas passiert
halt, wenn ein Kunstbetrieb mit wenig Geld auskommen muss.)

Es gab mal die Frage, von Lego in einem Preisausschreiben gestellt,
welches die ersten (Anzahl vergessen: drei, vier?*) Legofarben waren.

Ich glaube, es waren (in CA) weiss, rot und blau.
Gelb kam etwas später.

Wenn ich mich recht entsinne, kamen Schwarz und transparent erst,
als es ABS war.

Man sortiert seine LEgos ja nicht nach Farben, ...

Doch! Es gab z.B. 1965 einen Basiskasten mit roten und weissen,
einen anderen mit gelben und blauen. So wussten wir Geschwister
immer, wem was gehörte.

[image]


Avantgarde-Grüße zurück,
Ingo (war schon im schwedischen Kulturfernsehen, 6 Minuten mit LEGO-Kunst).


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


IngoAlthoefer
06.07.2016, 12:53

Als Antwort auf den Beitrag von Eisbär

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

LIeber Mich.a,

bitte vorsichtig sein, sonst verschreckst Du noch den Dietmar.
Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


drdwo
06.07.2016, 16:12

Als Antwort auf den Beitrag von cimddwc

Editiert von
drdwo
06.07.2016, 16:19

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

1.76e12

ist ca. Faktor 7.5 zu meiner Knotenzahl. Leider ist eine Stichprobe mit nur einem Element statistisch "etwas unsicher", es wäre jedenfalls ein Hinweis, das sich meine Verbesserungen der Suche beim 4-er stärker auswirken als beim 3-er (ca. Faktor 2).



drdwo
06.07.2016, 16:17

Als Antwort auf den Beitrag von IngoAlthoefer

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

Vielleicht kannst Du ja "trotzdem" probehalber den Code dieses Rechners
auf einen der vier anderen übertragen. Oder hat der Rechner vielleicht
ein anderes Verfahren, den Pseudozufall zu initialisieren?

Der Code war identisch wenn ich nichts übersehen habe. Bez. des Faktors 10 für 255/256 bin ich etwas skeptisch,
evtl. ist der Faktor größer. Bin auch unsicher ob man 80/81 er Verhältnisse beim 3-er auf das 4-er übertragen kann.



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)


Eisbär
15.07.2016, 08:58

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Kombinatorik-Rätsel auf LEGO-Basis

Liebär Ingo!

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.


k? Nicht n?

Und Auszählen? So richtig, mit Fingern? Oder Fünfer-Strichlisten?

Und wieso immer nur die Doppelvierer?

Da kommen dann ja phantasiellionen bei raus, wobei ich immer bezweifele, ob erstens alle identischen, bzw. symmetrischen Möglichkeiten herausgerechnet werden und zweitens, daß echte, real existierende Legosteine auf die Art und Weise auch wirklich zusammenhalten würden.

Soso, die Lehrämtler dürfen mit Legos spielen. Wo bleibt der Diskriminierungsombudsmann? Bzw. -frau.

Stimme aus dem OFF: Was bärechnen die Lehrämtlerinnen?

Den Unterschied zwischen Legokomplexen aus der Waschmaschine und der Trockentrommel?

Und überhaupt: Muß das sein? Darf man nicht einfach seine Legos aufeinanderstellen? So ganz mit ohne Snot und Rechnerei?

Unsereins wär ja schon froh, sie (die Legos) wären sauber, sortenrein sortiert und reichlich vorhanden. Und auffindbär. Neulich hat es hinterm Regal verdächtig geklötert.

Und warum findet man beim Sortieren immer die Sorten, mit denen man gerade fertig ist?

Klöterige Grüße
Mich.a



IngoAlthoefer
15.07.2016, 09:16

Als Antwort auf den Beitrag von Eisbär

Re: Kombinatorik-Rätsel auf LEGO-Basis

Lieb.er Eisbär!

Eisbär hat geschrieben:

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.

k? Nicht n?

Das ist das Tolle an Mathe. Buchstaben sind als Namen
(fast) beliebig austauschbar.

Und Auszählen? So richtig, mit Fingern? Oder Fünfer-Strichlisten?

Nee. Abstrakt mit dem Computer.

Und wieso immer nur die Doppelvierer?

Guter Einwurf. Antwort 1: Es gab eine Zeit, da war 4x2 der einzige Typ.
Antwort 2: Der nächste Student soll die 4x2-Ergebnisse auf 3x2 herunterrechnen.

...wobei ich immer bezweifele, ob erstens alle identischen, bzw.
symmetrischen Möglichkeiten herausgerechnet werden und ...

Das ist so, haben Dänen gemacht. Und die lügen bekanntlich nicht.

zweitens, daß echte, real existierende Legosteine auf die Art
und Weise auch wirklich zusammenhalten würden.

Richtig: stabil ist nur eine kleine Teilmenge. Und von der ist wieder die
Menge der in der Waschmaschine generierten Komplexe eine Teilmenge.

Soso, die Lehrämtler dürfen mit Legos spielen.

"Dürfen"? Nee: müssen!

Wo bleibt der Diskriminierungsombudsmann? Bzw. -frau.

Die stelle ich mit einem Päckchen "LEGO for friends" ruhig.

Stimme aus dem OFF: Was bärechnen die Lehrämtlerinnen?

Häkelmuster ?!

So: 2 Euro in die fiktive Machokasse, und Ruhe ist.

Legokomplexen aus der Waschmaschine und der Trockentrommel?

Beim Tockenschleudern bilden sich keine Komplexe. Da werden nur
die vorhandenen Steine an die Wand gedrückt.

Und überhaupt: Muß das sein? Darf man nicht einfach seine
Legos aufeinanderstellen? So ganz mit ohne Snot und Rechnerei?

Vor und nach dem Studium "ja". Zwischendrin ist Arbeiten angesagt.


Klöterige Grüße

Hmm. Weisst Du, was "klöterig" eigentlich bedeutet?

Jugendfreie Grüsse, ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Eisbär
15.07.2016, 09:59

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Kombinatorik-Rätsel auf LEGO-Basis

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.



Lok24
15.07.2016, 10:12

Als Antwort auf den Beitrag von Eisbär

Re: Kombinatorik-Rätsel auf LEGO-Basis

Eisbär hat geschrieben:

"irgendeine Zahl*", ....
*Von weiteren Delfinischohnen, wie ganze, natürliche, indiskrete usw. ist abzusehen.


Jaja, das sind schon rechte Plaudertaschen, die indiskreten Zahlen.



Eisbär
15.07.2016, 11:32

Als Antwort auf den Beitrag von Lok24

Re: Kombinatorik-Rätsel auf LEGO-Basis

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:

Die diskrete Mathematik als Teilgebiet der Mathematik befasst sich mit mathematischen Operationen über endlichen oder höchstens abzählbar unendlichen Mengen.


Nun denn. Ob ich daraus schlauer werde, bezweifele ich, denn bisher hatte ich doch naiverweise daran geglaubt, etwas unendliches sei nicht abzählbär, bzw. läge unendlich weit jenseits der von mich.abzählbären Grenzen. (Twünnich.)

Ganz davon ABSgesehen, daß es selbstverständlich ABßählbär (ganz eigentlich: ABSzählbär) hätte heißen gemußt, wobei das Problem des großen ß mal wieder deutlich wird.

Die indiskrete Mathematik als Obärgebiet der Mathematik befasst sich mit plaudernden Taschen über unendlichen und unzählbären endlichen Komplexen sowie deren Klöterigkeitskoeffizienten KK.**

Wäre es nicht ernsthaft mal an der Zeit, man (d.h. Ingo) erfände die indiskrete Mathematik?

Ungeahnte Auswirkungen auf das Zinswesen, die Sortierung von Waschmaschinen sowie die Verbindungsmöglichkeiten von Legos lassen sich kaum erahnen. Am Horizonte schweben zählbäre Erfolge in Form von gewaschenen Legos. Anstelle von sinnlos erscheinenden, willkürlich zugeordneten Buchstaben anstatt von Zahlen benützt man eindeutig zugeordnete Legos, muß aber darauf achten, bei der Zählung von dreitausend nach dreitausendundzwei die richtige Variante des Doppelvierers (unten ohne was, mit Schlitzen an der richtigen Stelle, bzw. den richtigen Stellen, mit ohne Logo, doch mit Logo, mit dïcker oder dünner Wand, mit unten rum doch was dran...(v.d.Z. gestr.), indiskret-mathematisch gesprochen befindet sich zwischen dreitausend und dreitausendundzwei ein sog. Klöterraum, der durch die Anzahl der real existierenden Legovarianten definiert wird und zwischen anderen Zahlen durchaus ganz anders gestaltet sein kann, zB zwischen 87852 und 87854 gibt es nur: 87853c01pb01, aber kein 87853 mit ohne was.

**Das, liebe Legoländer, ist hierzulande eine Zeitschrift, deren Titel übersetzt Frauen und Kleider so manchereinen dazu verleitet, nach dem indiskreten Pendant Frauen mit ohne (v.d.Z. gestr.)


Vor allem aber beschäftigt die indiskrete Mathematik sich auch mit dreiviertel Omnibussen und teilweise kaputten und klöternden Legos als entsprechendem Symbol.

Nu komms Du!

Diskrete Grüße
M.a



WolframBernhardt
29.07.2016, 23:40

Als Antwort auf den Beitrag von drdwo

Editiert von
WolframBernhardt
29.07.2016, 23:41

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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:


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



Viele Grüße,
Wolfram



WolframBernhardt
30.07.2016, 00:02

Als Antwort auf den Beitrag von WolframBernhardt

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

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 :-)



IngoAlthoefer
30.07.2016, 10:01

Als Antwort auf den Beitrag von WolframBernhardt

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Halo Wolfram,

willkommen bei den 1000steinern!

WolframBernhardt hat geschrieben:

Aus den obigen Diskussionen habe ich jetzt gelesen,
dass eher davon ausgegangen wird, dass die Steine nicht gedreht werden sollen.

Genau.

Das ist gut und erleichtert mir auch die "Arbeit" am 256er-Ding :-)

Willst Du etwa eine Lösung bauen, die auch
an den gegenüberliegenden Rändern passt?

Ingo.


LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)


Gesamter Thread: