Puzzles

27/06/2014 - 02:18 von Hans-Peter Diettrich | Report spam
Zu meinem letzten Geburtstag habe ich ein Puzzle mit 2000 Teilen
geschenkt bekommen, und beim Zusammensetzen hat sich mein Rücken heftig
beschwert - man wird einfach nicht jünger :-(

Nun habe ich festgestellt, daß es Roboter-Baukàsten gibt, mit denen es
eigentlich möglich sein sollte, die Einzelteile des Puzzles automatisch
zu katalogisieren und zusammenpassende Teile zu finden, so daß ich mich
dann sukzessive durch kleine Ausschnitte des Puzzles durcharbeiten kann.
Wie bei meinen Spline-Experimenten wàre auch hier der Weg das Ziel,
nicht eine vollautomatische Lösung für Puzzles.

Beim Betrachten eines fertigen Puzzles stellt sich zwangslàufig die
Frage, nach welchem Verfahren das Bild wohl in die Einzelteile
zerschnitten wurde. Kennt jemand so ein Verfahren, das z.B. zum
Herstellen eigener Puzzles verwendbar wàre?

Mein Ansatz dafür wàre eine Funktion, welche die Schnitte in
horizontaler bzw. vertikaler Richtung mit einer niedrigen Frequenz
"wellig" macht, und dann noch mit einer höheren Frequenz an jedem Rand
eines Teils für eine Ein- bzw. Ausbuchtung sorgt. In der Praxis könnte
man diese beiden Funktionen durch Random-Parameter so modifzieren, daß
die Teile nicht alle gleich aussehen. Bei der Katalogisierung der Teile
muß nun eine entsprechende Beschreibung der Kanten gefunden werden, die
diesem Verfahren möglichst nahe kommt, und zusàtzlich möglichst
unabhàngig von der Orientierung (Drehung) der Teile ist. Dazu habe ich
schon Ideen, wollte aber erst mal nach anderen Meinungen fragen.


Für die Katalogisierung der Teile stelle ich mir einen Roboter vor, der
mit einer Saugpinzette ein Teil aus dem großen Haufen holt und zur
Vermessung ein Bild davon anfertigt, z.B. mit einer Webcam. Das Bild
kann denn an einen Rechner geschickt werden, wo die weitere Verarbeitung
erfolgt. Die systematische Ablage der vermessenen Teile bereitet mir
noch Kopfzerbrechen, kann aber zunàchst vernachlàssigt werden. Ebenso
das Zusammensetzen des Puzzles, da ist wohl noch Handarbeit mit
Fingerspitzengefühl notwendig, das ich einem (einfachen) Roboter erst
mal nicht zutrauen würde. Auch bei den Farben der Teile bin ich noch
skeptisch, und möchte mich auch wegen der damit verbundenen Datenmenge
nicht nàher darauf einlassen. Zudem habe ich noch ein Puzzle in petto,
das fast nur aus Teilen etwa gleicher Farbe besteht, womit sich das
pattern matching auf den Verlauf der Kanten reduziert.

Zusàtzlich wàre noch die Ungenauigkeit der Messung zu berücksichtigen,
da die Rànder der Teile kaum in xy-Richtung der aufgenommenen Pixel
verlaufen, was eine gewisse Unschàrfe zur Folge hat. Dazu (pattern
matching) gibt es bereits Literatur, die mir (bzgl. Puzzles) allerdings
insgesamt etwas vage gehalten scheint. Zumindest erhoffe ich mir von der
Systematik des Verlaufs der Rànder eine Vereinfachung, die eine
Ermittlung möglicherweise zusammenpassender Teile mit einer
überschaubaren Datenbank und in genügend kurzer Zeit erlaubt.


Der mathematische Kern der Aufgabe làßt sich auch ohne Roboter und
Webcam untersuchen, wenn man eine Flàche systematisch in Teile mit oben
skizziertem Aussehen zerschneidet, die Teile ausmißt, in eine Datenbank
eintràgt, und darin dann systematisch nach zusammenpassenden Teilen
sucht. Womit sich der erste Teil der Aufgabe auf eine Funktion zur
Aufteilung der Flàche reduziert, gefolgt von einer *brauchbaren*
Beschreibung der Form der Teile (platzsparend, einfach 90° drehbar).

Für alle Ideen dankbar
DoDi
 

Lesen sie die antworten

#1 Rainer Rosenthal
27/06/2014 - 09:49 | Warnen spam
Am 27.06.2014 02:18, schrieb Hans-Peter Diettrich:
Zu meinem letzten Geburtstag habe ich ein Puzzle geschenkt bekommen, ...
Für alle Ideen dankbar



Nachtràglich noch alles Gute zum Geburtstag.
Klingt sehr spannend, was Du da ausprobieren möchtest, und es werden
wohl bald die ersten Miesepeter was von NP-complete und Knapsackproblem
erzàhlen, aber Hauptsache ist ja die Freude am Knobeln.

Das war die Überleitung zum neuesten, bereits seit Mai laufenden
Al Zimmermann Programmier-Wettbewerb "Alphabet City" zum Scrabble-Thema:
http://www.azspcs.net/

Der Wettbewerb làuft noch bis zum 17-ten August, Einsteigen lohnt sich
also. Ziel ist es, Scrabble ohne Gegner zu spielen und eine möglichst
hohe Punktzahl zu erreichen. Man weiß bereits, in welcher Reihenfolge
die 100 Buchstaben kommen werden, und die Joker-Regelung ist vereinfacht.
Es gibt 26 "Sàckchen" A, B, ... Z mit aufgereihten Steinen, und für
jedes Sàckchen bekommt man einen Score zwischen 0 und 1, kann also
maximal 26 Punkte insgesamt bekommen. Es sind gewisse Superpuzzler unter-
wegs, die weit über 20 Punkte haben, aber auch im unteren Punktebereich
kann man seinen Spaß haben.
Erstaunlich ist diesmal, wie hoch der Anteil menschlicher Intelligenz bei
den Bestlösungen ist.

Viel Vergnügen bei diesem technisch weitaus weniger anspruchsvollen Puzzle.
Ein Roboter, der die Teile aufs Scrabblebànkchen setzt und immer auf
Anzahl sieben auffüllt, bevor er weiter setzt, hàtte aber sicher einen
Sonderpreis verdient.

Ich habe mit den Sàckchen P bis U noch keine Bàume ausreißen können, aber
dabei sein ist Alles :-)

Herzlich grüßend und ein puzzliges Neues Lebensjahr wünschend,
Rainer Rosenthal

Ähnliche fragen