Kachelproblem

Ein Kachelproblem ist die Aufgabe, eine Menge von Teilen zu einem Gesamten anzuordnen, so dass bestimmte Regeln eingehalten werden. Kachelprobleme können als Rätsel zum Zeitvertreib gelöst werden. Die Theoretische Informatik untersucht Kachelprobleme, da hierbei Fälle von praktisch oder theoretisch unlösbaren Problemen auftreten.

Spiel

Kachelprobleme können als Legespiel umgesetzt werden. Bereits 1880 meldete Edwin Lajette Thurston ein solches Spiel zum Patent an.^[1] Die Kacheln können etwa gleichschenklige Dreiecke, Quadrate oder Sechsecke sein.

Jacques Haubrich teilt Kachelprobleme in sieben Kategorien ein:^[1]

1. Passende Seiten: Aneinanderliegende Seiten zweier Kacheln müssen die gleiche Farbe, Nummer, ... haben (Beispiel Domino).
2. Ober- und Unterteil: Statt wie bei den passenden Seiten gleiches zusammenzubringen, müssen hier zweigeteilte Paare zusammengebracht werden, etwa um Ober- und Unterteil einer Figur zusammenzubringen.
3. Pfade: Durch richtiges Aneinanderlegen entsteht ein an keiner Stelle unterbrochener Pfad.
4. Passende Ecken: An den Ecken der Kacheln sind Markierungen, die bei aneinanderliegenden Ecken übereinstimmen müssen (Beispiel Triominos).
5. Nicht passende Ecken: Die Eck-Markierungen dürfen nicht gleich sein.
6. Puzzle-artig: Neben eine Kachel passt höchstens eine der anderen Kacheln.
7. Mischformen

Die japanische Firma K.K. Takara-Tomy brachte mit Eternity II ein Spiel auf den Markt, bei dem 256 Teile passend auf ein 16 mal 16 Felder großes Raster gelegt werden müssen. Für die erste Lösung wurden 2 Millionen US-Dollar Preisgeld ausgelobt.^[2]

Kachelprobleme sind mit TetraVex als Computerspiel umgesetzt.

Theoretische Informatik

Die Grundform des Kachelproblems in der theoretischen Informatik ist die von rechteckigen Teilen, bei denen jede der vier Seiten eine bestimmte Zahl (auch: Farbe) zugeordnet ist. Ziel ist es, die Teile bündig so anzuordnen, dass bei aneinanderliegenden Seiten die beiden Zahlen übereinstimmen. Dabei kommt meist einschränkend hinzu, dass die Teile nicht gedreht werden dürfen.

Eine Ausprägung ist die einer endlichen quadratischen Fläche der Größe von n mal n Teilen, die mit den Elementen einer n * n Teile umfassenden Menge überdeckt werden soll. Festzustellen, ob es eine Lösung gibt, hat exponentiellen Aufwand. Wird jede mögliche Kachelung ausprobiert, übersteigt spätestens ab n=5 der Rechenaufwand das praktisch bewältigbare.^[3]

Bei einer weiteren Ausprägung des Problems ist der Umfang der zu kachelnden Fläche nicht fest vorgegeben. Die Elemente der Kachelmenge dürfen dann beliebig oft verwendet werden. Die zu beantwortende Frage ist nun, ob es möglich ist, mit der gegebenen Kachelmenge jede beliebige endliche Fläche regelkonform zu bedecken. Für dieses Problem ist es unmöglich, ein Programm zu schreiben, das die Frage in jedem Fall beantworten kann.^[4] Gleiches gilt für eine unendliche Ebene bei Wang-Dominos.

Einzelnachweise

1. ↑ ^{a b} Rob Stegmann: Pattern Puzzles: Edge Matching
2. ↑ Offizielle Website zu Eternity II
3. ↑ Solymosi/Grunde, S. 181 f.
4. ↑ Solymosi/Grunde, S. 175-177

Literatur

• Andreas Solymosi, Ulrich Grunde: Grundkurs Algorithmen und Datenstrukturen. 3. Auflage, Vieweg, Braunschweig/Wiesbaden, 2002.