Polyominos

Ein Polyomino ist eine Figur aus identischen Quadraten, die mindestens eine Seite gemeinsam haben. Wie das Wort andeutet, ist "Polyomino" eine Verallgemeinerung von "Domino". Das Präfix gibt jeweils an, aus wie vielen Quadraten die Figur besteht.

Zahlreiche Spiele der kombinatorischen Geometrie beruhen auf Polyominos. Es geht dabei um die Konstruktion einer bestimmten vorgegebenen Form oder um die Überdeckung eines Rechteckes nach bestimmten Kriterien. Auf der Basis der 12 Pentominos (Figuren aus 5 Quadraten) ist auch ein Spiel für zwei Personen erfunden worden.

Geschichte

Bereits 1907 veröffentlicht Henry Ernest Dudeney in "The Canterbury Puzzles" ein Pentomino-Problem. Im Jahre 1953 hält Solomon W. Golomb vor dem Harvard Mathematical Club einen Vortrag, in dem er den Begriff "Polyomino" einführt. Seine Arbeit wird ein Jahr später im "American Mathematical Monthly" publiziert. Das Interesse an Polyominos wächst mit der Veröffentlichung eines Artikels von Martin Gardner im "Scientific American" (Mai 1957). Im Jahre 1965 veröffentlicht Golomb sein Buch "Polyominoes", das in der Zwischenzeit ein Klassiker geworden ist.

Mathematik

Es gibt keine allgemeine Formel, um die Anzahl verschiedener Polyominos aus n Quadraten zu bestimmen. Die einzige Methode besteht darin, die Polyominos aus n Quadraten ausgehend von denjenigen aus n – 1 Quadraten explizit zu konstruieren. Dabei werden zwei Polyominos, die durch Drehung oder Spiegelung ineinander übergehen, als identisch betrachtet.

Viele Fragen zur Überdeckung eines Spielbrettes durch Polyominos können durch Einfärben der Felder elegant beantwortet werden. Der Beweis reduziert sich dann auf das Abzählen der Felder einer bestimmten Farbe. Auf diese Weise kann man z.B. zeigen, dass ein Schachbrett mit Dominos nicht überdeckt werden kann, wenn man die beiden weissen Felder in den Ecken entfernt hat. Die Anzahl schwarzer und weisser Felder müsste nämlich identisch sein.