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)

6 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

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

Permalink

1000steine-Code

BBCode

HTML


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!


62 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: