Max und Moritz, die beiden Werkstudenten, schoben den letzten von neun Tischen in einen Lagerraum im 67. Stock des Bürohochhauses. Hinter ihnen fiel die Tür ins Schloß.

"Jetzt ein Bier und eine Pizza", sagte Max schnaufend. Ihr Auftraggeber hatte ihnen verschwiegen, daß der Lastenaufzug nur bis zum 63. Stockwerk reichte. Die sperrigen Tische um die vielen Ecken der schmalen Treppe zu bugsieren war unerwartet mühsam gewesen.

Max kramte den Lieferschein hervor und hakte ab: "Zwei quadratische Eichentische, sechs rechteckige, davon vier mit Kiefer- und zwei mit Kunststoffplatte, und dann noch ein großer antiker Mahagonitisch."

"Stimmt", bestätigte Moritz. "Ist aber ziemlich eng hier."

"Ja, wirklich gerammelt voll. Tische von Wand zu Wand, ausgenommen da, wo wir stehen."

"Da haben wir Glück gehabt, daß sie auf Anhieb alle hineinpaßten."

"Allerdings." Max ließ einen wohlgefälligen Blick auf das vollbrachte Werk schweifen – und brüllte plötzlich los: "Nicht zu fassen! Da ist ein Loch in der Decke, und es tropft genau auf den teuren Mahagonitisch. Den müssen wir beiseite rücken."

"Das wird aber nicht einfach sein", meinte Moritz.

"Können wir die Tische vielleicht aufeinanderstapeln?"

"Geht nicht. Die Decke ist doch viel zu niedrig."

"Na schön. Dann schieben wir eben die zwei Kunststofftische unter das Loch und den großen Mahagonitisch in die andere Ecke" (Bild 1).

"Und wie?"

"Na ja – vielleicht die letzten zwei Tische aus dem Raum schaffen, dann müßte der Platz reichen, um..."

"Was? Noch zweimal diese ganze Millimeterarbeit?"

Das gefiel Max auch nicht. "Es ist doch Platz da, wo wir stehen", sagte er nach einigem Überlegen. "In die Lücke schieben wir einen Tisch, der läßt eine neue Lücke, und so weiter."

"Und wo passen wir hin?"

"Wir können ja unter den Tischen hindurchkriechen."

Dreißig Minuten und zahlreiche Flüche später war es ihnen gelungen, den antiken Tisch zur Mitte der rechten Wand zu schieben. Aber jetzt wurde einer der Kieferntische naß, und außerdem war die Tür verstellt (Bild 2).

"Wir brauchen einen Übersichtsplan", grübelte Moritz.

"Sonst geht's dir gut? Wir können die Tische doch alle sehen."

"Nicht einen Plan von dem Raum, sondern einen von dem Puzzle, das unser Problem ist."

Moritz starrte ihn an: "Was?"

"Ja, ganz abstrakt. Gedachte Landkarte. Jede Stellung der Tische ist ein Ort auf dieser Karte. Wir sind in X – das ist so, wie die Tische jetzt stehen – und wollen nach Y, das ist eine Stellung, bei welcher der Mahagonitisch trocken steht."

"Da gibt es mehrere Stellungen."

"Na schön, es genügt, einen solchen Ort zu finden. Gewisse Orte sind durch Straßen direkt miteinander verbunden. Wir suchen eine Straße, die über irgendwelche Dörfer von X nach Y führt."

"Das sind aber sehr viele Dörfer."

"Das kannst du wohl sagen. Also brauchen wir so etwas wie eine Übersichtskarte, die einem nicht den Weg von Dorf zu Dorf zeigt, sondern vielleicht immer zehn oder zwanzig Teilstrecken auf einmal. Aus solchen größeren Stücken können wir dann unseren Weg zusammensetzen."

"Ach so. Die große Karte zeigt nicht Dörfer, sondern Landkreise. Und von welchem Grenzpunkt eines Landkreises du zu welchem anderen kommst."

"Genau so ist es. Wie das tatsächlich im einzelnen zu machen ist, können wir uns hinterher auf der Fahrt in Ruhe genau anschauen."

"Und was ist ein Landkreis in deiner blühenden Phantasie?"

"Ach, das darfst du alles nicht so konkret sehen", erwiderte Max. "Stell dir einen abgegrenzten Teil dieses Lagerraums vor. Nur innerhalb darfst du Tische bewegen. Alle Stellungen, die du so erreichen kannst – das ist ein Landkreis."

"Also ein Teil vom Raum ist ein Landkreis?"

"Nein." Max wurde ungeduldig. "Die Menge der Stellungen mit der Eigenschaft, daß..."

"Ist ja gut. Also: Wenn du ein quadratisches Stück Raum hast mit den beiden kleinsten Tischen darin, kannst du sie ziemlich beliebig hin und her schieben."

"Genau. Es gibt noch einen etwas komplizierteren Teilraum; er ist doppelt so breit wie lang und enthält die beiden kleinen und zwei längliche Tische; da bleibt noch etwas Platz zum Schieben" (Bild 3).

"Man kann also Stellungen, die sich nur dadurch unterscheiden, daß Tische innerhalb eines Teilraums verschoben werden, als ziemlich gleich ansehen", sagte Moritz. "Dann gibt es etwas weniger Stellungen, über die man nachdenken muß."

"Viel weniger. Und gewisse Wege zwischen diesen Stellungen sind auch relativ übersichtlich. Es gibt nämlich manchmal nur eine sinnvolle Möglichkeit, die Tische weiterzuschieben, wenn du nicht rückgängig machen willst, was du schon erreicht hast."

"Ach so. Wenn du weißt, wo du bist, und weißt, wo du hinwillst, dann brauchst du solche Zugfolgen auf der Karte nicht einzuzeichnen."

"Jetzt hast du's erfaßt. Gib mir doch mal das Klemmbrett."


Der Plan

In kürzester Zeit hatte Max einen Plan skizziert, der einige der möglichen Positionen und Züge zeigte (Bild 4).

"Ich habe die Start- und die Zielstellung gekennzeichnet, außerdem gibt es noch sechs wichtige Zwischenstationen. Ich nenne sie A, B, C, D, E und F."

"Das sind aber nicht viele."

"Es gibt noch mehr. Das ist auch nur ein Teil der ganzen Landkarte. Aber es genügt, sich diese sechs zu merken. Jetzt hör zu. Die roten Verbindungslinien sind erzwungene Zugfolgen. Das heißt, wenn du Anfangs- und Endpositionen kennt, sind die Zwischenschritte offensichtlich, und es gibt nur eine Möglichkeit für jeden Schritt."

"Na schön."

"Prima. Die schraffierten Felder sind Teilräume, in denen Tische zu verschieben sind, ohne daß außerhalb etwas geschieht. Und zwar habe ich Anfangs- und Endstellung dieser Verschiebungen im Teilraum jeweils etwas kleiner neben das zugehörige große Bild gezeichnet."

Moritz tippte ziemlich hilflos auf der Karte herum.

"Paß auf. Stell dir vor, du willst wissen, wie man von C nach E kommt. Schau dir die rote Linie an, die diese beiden Positionen verbindet. Sie führt durch zwei kleine Diagramme. Setze jedes Diagramm an die Stelle des schraffierten Feldes im zugehörigen großen Bild – C beziehungsweise E. Dann hast du Anfangs- und Endposition der Zugfolge, die von C nach E führt. Die Züge dieser Folge sind erzwungen, deshalb findest du sie sehr schnell heraus – zum Beispiel, wenn du Pappstücke statt echter Tische herumschiebst."

"Aha. Und warum hast du ,Sackgasse' an den Weg unterhalb von Position F geschrieben?"

"Was meinst du wohl? Was sagst uns denn der Plan?"

"Der zeigt, wo die Dinger stehen und außerdem, wie sie von einer Stelle zur anderen kommen."

"Und noch viel mehr. Er sagt uns, wie man von ,Start' nach ,Ziel' kommt."

"Und zwar?"

"Zum Beispiel über C, A und B."

Moritz verfiel in tiefe Bewunderung für seinen Kollegen. "Kann man nicht auch über C, D und B irgendwie zum Ziel kommen?" fragte er.

"Sicher. Oder auch über C, E, F, D, B. Aber das wäre ein Umweg."

"Man kann auch C, D, F, E, C, D, B, A, B, D, C, E ..."

"Ja", unterbrach ihn Max, "wenn du noch so viel Puste hast. Ich bin mehr für den kürzesten Weg."


Noch mehr Puzzles

Nach einer Weile hatten Max und Moritz es geschafft, den antiken Tisch in Sicherheit zu bringen. Die zwei Kunststofftische standen unter dem Loch in der Decke, und die Tür war wieder frei zugänglich.

"Eigentlich war es gar nicht so schlimm", meinte Moritz im Gehen.

"Mit der Landkarte nicht mehr. Aber wir hatten Glück, es war eine ziemlich einfache. Es gibt eine ganze Menge Aufgaben dieser Art, die viel mehr erfordern als meine paar Tricks. Eine heißt Eselspuzzle. Wahrscheinlich hat man es im letzten Jahrhundert in Frankreich erfunden. Dann gibt es ungefähr seit 1980 das Jahrhundert-Puzzle; das ist ziemlich übel. Der kürzeste Lösungsweg besteht aus hundert Zügen. Und wenn du auch noch darauf bestehst, daß die Endposition genau ein Spiegelbild der Startposition ist, dann wird es erst richtig schwer. Diese Version nennt man Eineinhalb-Jahrhundert-Puzzle, denn man braucht dafür 151 Züge" (Bild 5).

Inzwischen waren sie im Erdgeschoß angekommen und wollten nur noch das eine: zum nächsten Schnellimbiß. Max schaute sich auf dem Parkplatz um – und brüllte abermals los: "Nicht zu fassen! Da hat ein Idiot sein Auto vor unserem Lastwagen abgestellt, und der ganze Platz ist gerammelt voll."

Moritz grinste hämisch. "Na und? In der Mitte ist noch eine freie Fläche. Wie wär's, wenn wir solange Autos verschieben, bis unseres frei ist?"

"Tolle Idee. Jetzt fängst du wahrscheinlich gleich an, mir zu erzählen, wie man einen Laster quer zur Fahrtrichtung verschiebt."

Literaturhinweise

- Gewinnen. Band 4. Von Elwyn R. Berlekamp, John H. Conway und Richard Guy. Vieweg, Braunschweig 1985.

– Mathematisches Labyrinth. Von Martin Gardner. Vieweg, Braunschweig 1979.


Aus: Spektrum der Wissenschaft 4 / 1996, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH