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)
IngoAlthoefer hat geschrieben:
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
Hallo Ingo,
IngoAlthoefer hat geschrieben:
\\//_ Build long and ℘rosper!
-jc- hat geschrieben:
Bricoon hat geschrieben:
\\//_ Build long and ℘rosper!
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