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:

Die 16 Teile in zufälliger Anordnung. 0 und 1 sind durch die Farben rot und blau ersetzt.

Meine einfache Konstruktion mit schwarzen Steinen als Unterschicht.

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)

---

Permalink

1000steine-Code

BBCode

HTML

---

Hallo Ingo,

IngoAlthoefer hat geschrieben:

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:
Wie von Dir richtig vermutet, teste ich von links nach rechts und danach von oben nach unten.

IngoAlthoefer hat geschrieben:
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:
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!

---

-jc- hat geschrieben:

Ich bin davon ausgegangen, dass der farbige 1x1 Stein immer links oben sein muss. Dann passt er nämlich nicht.

Gruß
Tobi Bricoon

---

---

Bricoon hat geschrieben:

Hallo Tobi,

stimmt, die Ausrichtung der weißen Kreuze muß bei allen Steinen identisch sein, denn sonst paßt es nicht.
Erst nachdem ich Dein ursprüngliches Posting mehrfach durchgelesen habe, ist mir aufgegangen, was genau Deine Frage ist, denn passende Steine gäbe es noch reichlich, aber Du hast Recht, daß es mit den verbliebenen Steinen unmöglich ist, das Gebilde auf eine Seitenlänge von 4 Teilen zu erweitern. Ich glaube, Du legst das Wort "Teillösung" zu eng aus. Ingo wollte lediglich zeigen, wie die Steine zusammen gelegt werden sollen. Er wollte damit nicht ausdrücken, daß man diese Anordnung tatsächlich als Grundlage für eine funktionierende Lösung hernehmen kann.

Gruß

Thomas

PS: So könnte eine gültige Lösung aussehen - noch 799 weitere Lösungen gilt es zu entdecken, wie Ingo und ich übereinstimmend ermittelt haben.

---

\\//_ Build long and ℘rosper!

---

Hallo,

da sich jedes Bild invertieren lässt, gibt es so gesehen "nur" 400 Lösungen
Also fehlen noch 398 *g*

Gruß
Jürgen

---

---

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:

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:
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:
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!

---

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:

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!

---

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!

---