Hallo,
aus den 1950er Jahren stammt ein Puzzle, wo 4 x 4 Teile
so aneinander zu legen sind, dass alle Übergänge passen.
Der Schöpfer (Hans Bouwmeester aus den Niederlanden?!)
beschrieb es mit 16 Pappkärtchen, wo auf jedem ein bestimmtes
Muster aus vier Nullen/Einsen abgebildet war. Jede der
2 hoch 4 Möglichkeiten kam genau einmal vor.
Schon vor einiger Zeit habe ich dieses Puzzle mit LEGO-Steinen
realisiert:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
doktorjoerg , Custer , Cran , Seeteddy , Legomichel , Dirk1313 , renrew , Legobecker , Plastik , MARPSCH , fannie1981 , Lukutus , cimddwc , doe , uefchen , Titus , naseneis , nvneuss , JuL (19 Mitglieder)
Hallo,
jetzt hat's mich auch gepackt und ich hab auch ein Progrämmchen geschrieben (bzw. 3 Varianten, jeweils angepasst).
Vorgehensweise:
- 2 Listen erstellen, in denen für jeden Stein angegeben ist, welcher rechte bzw. untere Nachbar möglich ist
- nach und nach Felder durchgehen, bei möglichen Steinen weiterprobieren mit den nächsten Feldern, ansonsten zurück. (Ist das Backtracking?)
Und das ganze schön optimiert in x86-Assembler. Die 2-Farb-Variante (dafür reichen die normalen 32-Bit-Register (sogar 16 Bit würden reichen)) findet die 800 Lösungen nach ca. 80.000 Versuchen in ca. 2 Millisekunden.
Die 3- und 4-Farb-Variante benutzen die 256-Bit-Register von AVX2 - allerdings mit dem Problem, dass die Suche des nächsten möglichen Steins nicht so schön effizient ist wie mit den normalen Registern. Oder kennt jemand eine gute BSF-Variante für AVX2-ymm-Register?
Wobei ich sagen muss, dass das recht schnelle Versuche waren - ich hab zwar einige gefundene (Teil-)Lösungen kontrolliert, kann mir aber gerade bei den 3- und 4-Farb-Varianten nicht wirklich 100% sicher sein, dass alles stimmt... theoretisch sollte es jedenfalls.
Das 3-Farben-Programm läuft noch, nach 41 Minuten war's bei 560.000 Lösungen und 100 Mrd. Versuchen angelangt. Na hoffentlich stimmt das auch...
Das 4-Farben-Programm läuft noch nicht so lange, das hat nach 7,5 Sekunden schon 246 Steine nach 350 Mio. Versuchen verbaut und eben nach ca. 7,5 Minuten waren's 250 Steine nach 19,8 Mrd Versuchen. Aber noch keine komplette Lösung.
Grüße,
Andreas
Hallo Andreas,
cimddwc hat geschrieben:
\\//_ Build long and ℘rosper!
Hallo,
Ich werd morgen nochmal weitere Lösungen unter die Lupe nehmen, ob da nicht zu viele dabei sind. Jedenfalls schläft mein Rechner über Nacht, der letzte Stand bei 4 Farben war nach 184min 252 Steine bei 482 Mrd Versuchen.
Grüße,
Andreas
Mir ist grad noch was eingefallen: ich glaub, ich zähl die Versuche falsch. Der Zähler wird erhöht, wenn in einem Feld n kein Stein mehr möglich ist (sodass das eben als Versuch fürs Feld n-1 zählt). Aber beim Zurückgehen, wenn das auch die letzte Möglichkeit für n-1 war und es weiter zu n-2 zurückgeht, wird er nochmal erhöht, u.s.w., und das wäre dann immer etwas zu viel...
Grüße,
Andreas
cimddwc hat geschrieben:
\\//_ Build long and ℘rosper!
Ich geb's auf!
Nach etlichen Milliarden Versuchen habe ich über 21.000 Lösungen für das 3-Farb-Puzzel gefunden, aber keine einzige für 4 Farben. Mein bestes Ergebnis waren 237 von 256 Teilen. Nachdem ich weiter oben in diesem Thread mal die Kombinationsmöglichkeiten für 2 Farben durchgerechnet hatte, wage ich nicht einmal ansatzweise darüber nachzudenken, wie viele Nullen wohl die Zahl der Versuche haben mag, die sich bei 3 und 4 Farben ergeben... Selbst abzüglich der übersprungen Möglichkeiten übersteigt dies meine Kapazitäten, um in einem überschaubaren Zeitraum zu einem endgültigen Ergebnis zu kommen.
\\//_ Build long and ℘rosper!
Nun, ich werd' nächste Woche noch weiterrechnen lassen (übers Wochenende bleibt der PC aus), 253 Steine hat das 4er-Programm mittlerweile erreicht; Zwischenstand beim 3er sind 4,2 Mio. Lösungen.
(Rechenzeit kann ich leider nicht angeben, weil die ausgegebene sich dummerweise auf die Uhrzeit des Starts bezieht...)
Grüße,
Andreas
Hallo Andreas,
cimddwc hat geschrieben:
LEGO kennt kein Valsch (alte Klemmbaustein-Weisheit)
Hi.
Interessant, da juckt es mich fast wirklich mir die Teile für den Nachbau zu besorgen.
Eine Frage aber:
Kirk schrieb: