© Diego Cervo, 123RF

Das fast zweitausend Jahre alte Geduldsspiel “Chinesische Ringe” landete bei Mike Schilli. Statt nur mit Ringen zu klimpern, versucht er sich an einer Lösung mit logischen Operatoren.

Mangels Geduld bin ich kein Freund von Geduldsspielen, aber als ich neulich in einem Online-Antiquariat in Martin Gardners ehrwürdiger “Scientific American”-Kolumne aus dem Jahr 1972 [2] las, dass sich das “Chinesische Ringe” genannte Puzzle mit Gray-Codes [3] aus der Informationstheorie lösen lässt, erfasste mich doch das Spielfieber. Ich bestellte mir kurzerhand das Ring-Set für kleines Geld.

Ein chinesischer General namens Chu-ko Liang soll das Spiel, das den Namenszusatz “Baguenaudier” (Zeitverschwender) [4] trägt, im zweiten Jahrhundert erfunden haben, um seine Ehefrau während seiner Abwesenheit zu beschäftigen. Es kam in einem Karton mit aufgedruckten chinesischen Schriftzeichen an, und ich spannte die Leiste mit den silbernen Ringen sogleich in weiser Voraussicht auf eine langwierige Fummelei in meinen Schraubstock für Elektronikbasteleien.

Die neun unscheinbaren Ringe liegen anfangs alle auf einer vorne geschlossenen Metallschiene mit Mittelspalt und kleine beweglich an den Ringen befestigte Metallstänglein fixieren sie an einer weiter unten liegenden Metallleiste (Abbildung 1). Diese restriktive Aufhängung vermittelt zunächst den Eindruck, als ließe sich an der gesamten Konstruktion nichts bewegen, aber in der beiliegenden Gebrauchsanweisung standen Hinweise darauf, welche eingeschränkten Zugmöglichkeiten bestehen.

Abbildung 1: Am Anfang liegen alle neun Ringe auf dem Metallrahmen.

Zug um Zug

Der Spieler bewegt pro Zug einen Ring, indem er ihn durch den Mittelspalt der Schiene führt, entweder um ihn auf die Schiene zu heben oder um ihn von dort zu entfernen und durch die Schienenöffnung nach unten zu bugsieren. Das Spiel unterliegt genau zwei Beschränkungen: Der erste (rechts außen liegende) Ring ist jederzeit frei beweglich. Alle anderen Ringe lassen sich nur dann bewegen, wenn a) ihr direkter rechter Nachbar oben auf der Schiene ist und b) alle weiteren Ringe zur Rechten bis zum Schienen-Ende unten liegen.

Bei der Anfangskonstellation in Abbildung 1 sind also zwei Züge möglich: Der Spieler kann den ersten Ring nach rechts abziehen, hochheben, querstellen und dann durch die Mittelöffnung der Schiene nach unten sausen lassen. Lässt der Spieler den ersten Ring in Ruhe, kommt alternativ der zweite Ring auf der Schiene in Betracht. Da der zweite Ring von rechts nur einen Ring zur Rechten hat (Ring Nummer eins), der auch noch oben auf der Schiene liegt, kann ersterer nach unten bugsiert werden.

In diesem Fall schiebt der Spieler den rechten Ring noch etwas weiter nach rechts bis über das Schienen-Ende hinaus (ohne ihn fallen zu lassen) und zieht gleichzeitig den zweiten Ring ebenfalls nach rechts, führt ihn nach rechts aus der Schiene heraus, stellt ihn dann quer und schubst ihn durch den Schienenspalt nach unten.

Gleiches gilt, um einen Ring von unten nach oben zu bugsieren, in Abbildung 2 liegt Ring vier unten, während Ring drei oben liegt und die Ringe zwei und eins unten. Nach den Regeln darf der Spieler Ring vier durch den Spalt in der Leiste nach oben heben, an Ring drei nach rechts am Leistenrand vorbeiführen, von rechts in die Leiste einfädeln und dann ablegen (Abbildung 3).

Abbildung 2: Ring drei ist oben, die Ringe eins und zwei unten, also kann Ring vier …

Abbildung 3: … hochgezogen und unter Ring drei hindurch oben platziert werden.

Wie man auf Wikipedia [3] nachlesen kann, lassen sich alle neun Ringe des Puzzles in insgesamt 341 Zügen abbauen, sodass am Schluss erstaunlicherweise tatsächlich nur die leere Leiste übrig bleibt. Das absolut nervtötende an dem Verfahren ist aber, dass der Spieler dazu Dutzende Male zurücksetzen muss, denn um zum Beispiel Ring neun abzunehmen, muss Ring acht oben, aber die Ringe eins bis sieben unten liegen.

Wie kommt Ring sieben, der sich anfangs wie alle anderen Ringe oben befindet, nach unten? Indem Ring sechs oben liegt, während eins bis fünf unten sind. Wie kommt fünf nach unten? Indem vier oben liegt, während eins bis drei unten liegen.

So geht das immer hin und her, bis schließlich erst Ring neun unten liegt, dann Ring acht – bis schließlich bei Zug 341 Ring eins abfällt. Allgemein ist die Formel für die minimale Anzahl der Züge für ungerade Ringzahlen 2ⁿ⁺¹ – 1/3, steigt also exponentiell mit der Zahl der Ringe an.

Dabei muss der Spieler genau überlegen, welchen Ring er als nächsten umlegt, bewegt er sich in die falsche Richtung, muss er später wieder umdrehen und alles zurückfahren, weil er sich sonst im Kreis dreht und nicht vorwärtskommt.

Auf geht’s, Automat!

Auf den ersten Blick erinnern die repetitiven Spielzüge mit den Ringen an binäre Zahlen, aber diese ändern mehr als ein Bit auf einmal, man denke nur an die Folge »0111« (5) zu »1000« (6), wo sich auf einen Schlag 4 Bits oder Ringe ändern. Anders verhalten sich so genannte Gray-Codes [3], die bei jedem Schritt jeweils nur 1 Bit ändern. Statt »00«, »01«, »10«, »11« zählt der nach dem Physiker Frank Gray benannte Gray-Code »00«, »01«, »11«, »10«. Binärzahlen wandelt folgende Formel nach [3] in Gray-Code um: »num XOR (num >> 1)«.

Aus der Zahl 3 (binär »10«) wird so zum Beispiel durch den einbittigen Bitshift nach rechts »01« und der X-OR-Operator (^) verbindet »10« und »01« zu »11«, da er immer dann anschlägt, wenn die Bits beider Operatoren sich an einer Stelle unterscheiden. Listing 1 implementiert mit der Funktion »grayme()« dieses simple Verfahren. Den XOR-Operator holt es aus dem Paket »operator« als Funktion »xor()«.

01 #!/usr/bin/env python3
02 import operator
03
04 def grayme(num):
05     shifted=num>>1
06     return(operator.xor(num,shifted))
07
08 def main():
09     for i in range(15):
10         print(i, format(i,"08b"),
11               format(grayme(i),"08b"))
12
13 if __name__ == "__main__":
14     main()

Als praktischer Test iteriert die For-Schleife in der Funktion »main()« ab Zeile 8 über die Zahlen von 1 bis 14 und gibt in jeder Runde die Zahl im Dezimalsystem, als Binärzahl und als Gray-Code aus (Abbildung 4). Python bietet bekanntlich (entgegen seiner Philosophie “There’s one way to do it”) drei verschiedene Verfahren zur String-Formatierung à la »printf()« an. Listing 1 nutzt die Core-Funktion »format()«, die Integer mit dem Formatstring »08b« 8 Bit breit als Binärzahl mit führenden Nullen ausgibt, weiter die Dezimalzahl »i« selbst und den daraus mit »grayme()« generierten Gray-Code.

Abbildung 4: Gray-Codes der Zahlen 1 bis 14 geben die schnellste Transformation an.

Läuft nur als Kommando

Das Python-typische »if __name__ == “__main__”« prüft, ob das Skript von der Kommandozeile aus aufgerufen wurde, und springt in diesem Fall in die Funktion »main()« ab Zeile 8. Falls das Skript allerdings als Paket per »import graycode« in ein anderes Skript hineingezogen wurde, führt es den »main()«-Code nicht aus, sondern bindet die Funktion »grayme()« in das Skript ein, das sie dann als »graycode.grayme()« nutzen kann.

Alternativ kann ein Python-Skript die Funktion aber auch mit Hilfe von »from graycode import grayme« direkt in ihren Namespace importieren, sodass dort einfach »grayme()« funktioniert.

Test im Pudding

Beim Überfliegen der Gray-Codes in Abbildung 4 sieht die Ausgabe nach einer brauchbaren Lösung des Ringproblems aus. Baut der Spieler Ringe ab, stellen die Nullen im Gray-Code die oben liegenden Ringe dar, fädelt er die Ringe später wieder auf die Schiene auf, sind die 0-Bits die unten liegenden Ringe.

Doch stimmt das Verfahren auch im Detail? Ein Testskript soll alle Codes durchgehen und zu jedem die zwei Bedingungen des Spiels prüfen: Wird jedes Mal wirklich nur ein Ring bewegt, entweder von oben nach unten (»0=>1«) oder von unten nach oben (»1=>0«)? Und bewegt der Spieler nur den ersten Ring oder, falls ein anderer Ring an der Reihe ist, steckt sein rechter Nachbar wie gefordert oben auf der Leiste und sind alle anderen Ringe zu seiner Rechten unten? Mit Pythons Bit-Operationen geht es nun dem Gray-Code an den Kragen.

Die Utility-Funktion »bits_set()« ab Zeile 10 in Listing 2 durchforstet die Bits einer Zahl und gibt einen Array mit den Indexnummern der auf 1 gesetzten Bits zurück. Sie dient unter anderem als Maß dafür, dass ein Gray-Code erreicht ist, bei dem alle neun Ringe oben sind, nämlich wenn der erste neun-elementige Array mit Indexnummern erscheint.

Weiter prüft das Testskript, wie viele und welche Bits sich von einem Gray-Code zum nächsten verändert haben, und stellt sicher, dass jedes Mal nur 1 Bit (also ein Ring) bewegt wurde. Dazu verknüpft die Funktion »rings_changed()« ab Zeile 6 zwei Gray-Codes mit dem XOR-Operator, der im Resultat Bits an den Stellen auf 1 setzt, die sich verändert haben.

01 #!/usr/bin/env python3
02 import operator
03 import math
04 from graycode import grayme
05
06 def rings_changed(pos1,pos2):
07     xor = operator.xor(pos1,pos2)
08     return bits_set(xor)
09
10 def bits_set(num):
11     bits = []
12     while True:
13         if num == 0:
14             break
15         bit = int(math.log(num,2))
16         mask = 1 << bit
17         num  &= ~mask
18         bits.append(bit)
19     return(bits)
20
21 def move_valid(pos1,pos2):
22     changed=rings_changed(pos1, pos2)
23
24     if len(changed) != 1:
25         # right-most ring or next ring set?
26         raise Exception(
27           "More than one change: " +
28           str(changed))
29
30     if changed[0] != 0:
31         # next ring up?
32         mask = 1 << changed[0]-1
33         if not (pos2 & mask):
34             raise Exception(
35               "Next ring not up: " +
36               str(changed))
37
38         if changed[0] > 1:
39             # right-most rings down?
40             mask = ~(~0 << changed[0]-1)
41             rest = pos2 & mask
42             if len(bits_set(rest)) != 0:
43                 raise Exception(
44                   "Rings not down: " +
45                   str(changed))
46 def main():
47     i=0
48     rings=9
49     last_gray=None
50     while True:
51         gray=grayme(i)
52         print(format(gray,"08b"))
53
54         if last_gray is not None:
55             move_valid(last_gray, gray)
56
57         last_gray=gray
58
59         if len(bits_set(gray)) == rings:
60             break
61
62         i += 1
63
64 if __name__ == "__main__":
65     main()

Dann zählt die Schleife ab Zeile 12 die 1-er Bits im Resultat und hängt ihre Indices mittels »append()« an den Array »bits« an, den die Funktion am Ende zurückgibt (Abbildung 5). Den Index des höchsten gesetzten Bit der zu untersuchenden Zahl ermittelt es mit der Formel »int(math.log(num,2))«, die den Logarithmus der zu untersuchenden Zahl zur Basis 2 errechnet und ihn auf den nächsten Integerwert abrundet. Um das Bit dann zu löschen, generiert es eine Maske mit einem an der kritischen Stelle gesetzten Bit und verknüpft die Zahl und die Maske mit einem Bit-weisen Und-Operator:

Abbildung 5: Mittels Xor prüft das Testskript, welche Ringe der User nach dem Gray-Code verschiebt.

mask = 1 << bit
num  &= ~mask

Die nächste Runde der Schleife findet eventuell weitere Bits auf den niedrigeren Rängen, bis die Zahl den Wert 0 annimmt und die Schleife abbricht.

Ob ein vom Gray-Code vorgeschlagener Zug gültig ist, prüft die Funktion »move_valid()« ab Zeile 21. Erst wirft sie eine Exception, falls sich mehr als ein Bit (Ring) geändert hat (Zeile 26), deswegen prüft das Hauptprogramm ihren Rückgabewert erst gar nicht. Für Ring zwei und höher prüft das If-Konstrukt ab Zeile 30 mit einer Maske, ob der nächste Ring rechts oben liegt, und bricht andernfalls in Zeile 34 mit einem Fehler ab.

Für die Ringe drei und höher prüfen Zeilen 39 und folgende mit einer Einsermaske, ob alle rechts liegenden Ringe unten sind.

Einsermaske

Eine Maske mit »n« rechtsbündigen Einsen erzeugt das etwas seltsame Konstrukt

~(~0 << n)

in Zeile 40. Mit »~0« legt es zunächst das Bit-Komplement der Zahl »0« an, also einen Integer, bei dem alle Bits auf 1 gesetzt sind. Den »bit-shifted« es dann um »n« Stellen nach links, was die ersten »n« rechtslastigen Bits von rechts mit Nullen auffüllt, während der Rest der Zahl bei 1-Bit-Werten verharrt.

Ein weiteres Komplement »~« außerhalb der Klammer dreht noch einmal alle Bits um, sodass die Maske wie gewünscht die ersten »n« Bits von rechts auf 1 gesetzt hat. Abbildung 6 zeigt schließlich die Ausgabe des Testskripts und verifiziert damit, dass der Gray-Code alle Regeln des Ringspiels einhält.

Abbildung 6: Das Testskript überprüft 341 Übergänge nach Gray-Code auf ihre Gültigkeit im Puzzle.

Das Bit-weise Verfahren taugt nichts bei größeren Ringzahlen, funktioniert aber bis zur Integergrenze von 32 oder 64 Bit, je nach Plattform. Ringspiele mit mehr als zehn Ringen sind ohnehin nicht praktikabel, da die Kombinationen zahlenmäßig explodieren. Das Spiel ist ein schöner Zeitvertreib (Abbildung 7), kann aber auch zum Nervenzusammenbruch führen. Wichtig ist, die Züge zum nächsten zu entfernenden Ring zu planen. Es ist frustrierend, wenn der Spieler einen Ring, der oben bleiben müsste, um einen anderen zu entfernen, im Eifer des Gefechts entfernt. Er muss dann in seinen Fußstapfen zurückmarschieren. (uba)

Abbildung 7: Nach etwa 250 Zügen, kurz vor der Lösung des Puzzles.