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)

18 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

-jc-
23.06.2016, 14:16

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen

Permalink

1000steine-Code

BBCode

HTML


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



50 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: