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.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


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.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


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.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


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.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


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.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


68 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: