What puzzles me

16. Dezember 2009 von Jedi

Man stelle sich vor, vor einem liegen n Puzzleteile. Eines davon hält man fest und probiert alle anderen (n-1) Teile, daran zu befestigen. Es ist leicht einzusehen, dass man dabei durchschnittlich nach \frac{n-1}{2} Teilen Erfolg hat.

Nach diesem Erfolgserlebnis, existieren natürlich nur noch n-2 Puzzleteile überprüft werden und der Erfolg wird sich vermutlich nach \frac{n-2}{2} Teilen einstellen.

Insgesamt müssen also vermutlich \frac{1}{2}\sum\limits_1^{n-1} Teile in die Hand genommen werden, oder wie wir spätestens seit Gauß wissen: \frac{1}{2}\frac{n(n-1)}{2}, also \frac{n(n-1)}{4}.

Das vorliegende Puzzle hat 1008 Teile. Einsetzen und Ausrechnen überlasse ich dem Leser.

Nun könnte dieser einwenden, dass obige Annahmen sehr naiv sind, sie davon ausgehen, dass man beim Puzzlen keine weiteren Informationen benutzen kann, man stumpfsinnig jedes Teil an jeder Stelle ausprobiert.

Der Einwand ist richtig, weshalb die Annahmen auch nur auf die rund 272 weißen Teile zutreffen, die nicht gleichzeitig Randteile sind. Selbst da kann durch geschicktes Sortieren oft vermieden werden, jedes Teil zu testen - oft aber auch nicht.

Wie dem auch sei, die Zahlen sind abschreckender als die Realität, denn dort gibt es doch effizientere Wege, als Brute Force. So war der Rand in kürzester Zeit fertig gestellt.

Der Rand ist fertig.

Der Rand ist fertig.

Anschließend gab es schwarze, weiße und schwarz-weiße Teile. Letztere unterteilten sich noch in solche, auf denen die schwarzen Striche durchgehend waren und solche, die mitten auf dem Teil endeten. Letztere waren wieder einfach zu platzieren.

Der Rand des Barcodes ist fertig.

Der Rand des Barcodes ist fertig.

Auch dieser schritt war schnell erledigt. Jetzt konnte der Zwischenraum ausgefüllt werden. Da die Streifen unterschiedlich breit sind, war auch das nicht weiter schwierig.

Erste Striche sind fertig.

Erste Striche sind fertig.

Ganz wichtig: 90 Prozent der Zeit wurde nicht für das Ausprobieren der Teile genutzt, sondern für das Sortieren der Teile.

Hier sind die Teile nur grob sortiert.

Hier sind die Teile nur grob sortiert.

Mit 90 Prozent sind wohl eigentlich 95 Prozent gemeint.

Hier sind die Teile schon etwas besser sortiert.

Hier sind die Teile schon etwas besser sortiert.

Als nur noch weiße Teile übrig waren, bot sich den Besuchern der eigens für dieses Puzzle eingerichteten BCPP (Bar Code Puzzle Progress) - Homepage folgender Anblick:

Fortschritt, als nur noch weiße Teile fehlten.

Fortschritt, als nur noch weiße Teile fehlten.

Der Rest war tatsächlich Brute Force, manchmal mehr Brute als Force. Das Ergebnis kann sich jedoch sehen lassen und hängt nun an der Wand. 70×50 cm waren einfach zu groß um das Schild an der Klingel oder am Briefkasten ersetzen zu können.

Eine Antwort hinterlassen