Die Körbe von Hanoi //2347

Wenn ich abends Wäsche sortiere, kann das ziemlich kompliziert werden. Da gibt es Bettwäsche, Handtücher, Sachen von Carsten, Sachen von mir, große Teile wie Jacken, kleine Teile wie Unterwäsche oder Socken. Teilweise soll das ins Landhaus, teilweise bleibt es hier in der Stadtwohnung. Dass Zeug muss in unterschiedliche Schränke, Bügelwäsche separat. Dann habe ich noch die Marotte, Bettwäsche unten in den Waschkorb zu legen, die anderen Sachen in zwei Stapeln obendrüber.
Normalerweise sortiere ich nach jeder Maschinenwäsche nach dem Trocknen. Diesmal war ich jedoch nicht dazu gekommen, und inzwischen zwei Waschmaschinenladungen aufgelaufen. So saß ich also auf dem Sofa mit drei Waschkörben vor mir, teils mit bereits fertig zusammengelegter Wäsche, teils noch unsortiert und ungefaltet.
Um die größeren Stücke unter die zusammengefalteten kleineren Teile zu bringen, musste ich teilweise die fertige Wäsche in einen anderen Waschkorb wechseln, als plötzlich eine uralte Erinnerung in mir hochstieg ..

Die „Türme von Hanoi“ ist ein altes Spiel, über das ich einst als Kind (mit vielleicht 10? – ich weiß es nicht mehr) in einem Buch gelesen hatte, und mir selbst aus Pappkarton gebastelt hatte. Mit Münzen wäre es auch gegangen.
Dabei gibt es drei Stapel mit insgesamt n unterschiedlich großen Scheiben. Am Anfang liegen alle Scheiben der Größe nach geordnet auf einem Stapel. Die Aufgabe ist es, alle Scheiben auf einen anderen Stapel zu bringen. Dabei darf bei jedem Spielzug nur eine Scheibe umgelegt werden, und zwar nur auf eine größere Scheibe (oder einen leeren Stapel). Keinesfalls darf eine Scheibe auf einer kleineren liegen.
Das kann man erst einmal für ein kleines n (z.B. 5) probieren. Ich erinnere mich nicht mehr sicher, glaube aber, dass ich acht Scheiben (bzw. Pappstücke) hatte.
Da war ich erst mal beschäftigt, während ich spielerisch ausprobierte, wie die Scheiben hin- und hergelegt wurden. Der ursprüngliche Stapel wurde kleiner, der neuer Stapel wuchs.
Und wie ich so vor mich hin spielte, erkannte ich, dass man die Scheiben auf eine ganz bestimmte Weise umlegen musste, um den neuen Stapel möglichst rasch aufzubauen. Diese spezielle Vorgehensweise faszinierte mich. Ich hatte damals keine Ahnung, dass das, was ich herausgefunden hatte, ein Algorithmus war.

Ich werde es euch ersparen, hier haarklein den Algorithmus zu beschreiben. Überlegt ihn euch selbst.
Hier nur einige Hinweise, wie man das Problem (ohne Objektifizierung, aber mit Digitalisierung) mit dem Computer angehen könnte.
Wir ordnen jeder Scheibe von oben nach unten ein Bit zu. Die kleinste Scheibe entspricht 1, die zweite 2, die dritte 4, die i-te 2^i bis zur untersten mit 2^n. Dann beträgt der Wert des Anfangsstapels, also die Summe aller Scheibenwerte, 2^(n+1) – 1, die Werte der leeren Stapel jeweils 0. Durch diese drei Werte der einzenen Stapel lässt sich der aktuelle Zustand des Systems eindeutig beschreiben. Es ist zu beachten, dass die Summe der Werte aller Stapel konstant, also 2^(n+1) – 1 bleibt.
Als Kriterium, ob es erlaubt ist, die i-te Scheibe mit dem Wert 2^i = k umzulegen, muss der k-Modulo des Wertes des Zielstapels gleich 0 sein. Das bedeutet, wie ihr euch leicht selbst überlegen könnt, dass keine kleinere Scheibe bereits oben vorhanden ist.