Mangels Geduld bin ich ja eigentlich kein Freund von Geduldsspielen, aber als ich neulich in einem Online-Antiquariat in Martin Gardners ehrwürdiger "Scientific American"-Kolumne aus dem Jahr 1972 ([5]) las, dass sich das "Chinesische Ringe" genannte Puzzle mit Gray-Codes aus der Informationstheorie lösen lässt, erfasste mich doch das Spielfieber und ich bestellte mir kurzerhand auf Amazon das Ring-Set für kleines Geld. Es kam in einem Karton mit aufgedruckten chinesischen Schriftzeichen an, und ich spannte die Leiste mit den silbernen Ringen sogleich in weiser Vorraussicht auf eine langwierige Fummelei in meinen Schraubstock für Elektronikbasteleien (Abbildung 1). Statt meine Zeit aber mit dem tatsächlich "Baguenaudier" (Zeitverschwender) genannten Spiel zu vergeuden, das angeblich ein chinesischer General namens Chu-ko Liang im zweiten Jahrhundert erfunden hat, um seine Ehefrau während seiner Abwesenheit zu beschäftigen, malte ich mir aus, dem langwierigen Verfahren mit auf dem Web einsehbaren mathematischen Prinzipien zuleibe zu rücken und es automatisch zu lösen.
| |
| Abbildung 1: Am Anfang liegen alle neun Ringe auf dem Metallrahmen. |
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 Metalleiste. Diese restriktive Aufhängung vermittelt zunächst den Eindruck, als ließe sich an der gesamten Konstruktion praktisch gar nichts bewegen, aber in der beiliegenden Gebrauchsanweisung standen Hinweise darauf, welche eingeschränkten Zugmöglichkeiten bestehen.
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 ihn von dort zu enfernen und durch die Schienenöffnung nach unten zu bugsieren. Das Spiel unterliegt genau zwei Beschränkungen: Der erste (rechteste) Ring ist jederzeit frei beweglich und 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 Schienenende unten liegen.
Bei der Anfangskonstellation in Abbildung 1 sind demnach zwei Züge möglich: Der Spieler kann den ersten Ring nach rechts abziehen, hoch heben, querstellen, und dann durch die Mittelöffnung der Schiene nach unten sausen lassen. Lässt der Spieler den ersten Ring in Ruhe, kommt alternativ auch 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 Schiene liegt, kann ersterer nach unten bugsiert werden. In diesem Fall schiebt der Spieler den allerrechtesten Ring noch etwas weiter nach rechts bis über das Schienenende 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 4 unten, während Ring 3 oben liegt und die Ringe 2 und 1 unten. Nach den Regeln darf der Spieler Ring 4 durch den Spalt in der Leiste nach oben heben, an Ring 3 nach rechts am Leistenrand vorbeiführen, von rechts in die Leiste einfädeln und schließlich ablegen (Abbildung 3).
 |
| Abbildung 2: Ring drei ist oben, Ringe eins und zwei unten, also kann Ring vier ... |
 |
| Abbildung 3: ... durch den Mittelspalt hochgezogen, und unter Ring drei hindurch von vorne über die Schiene gestülpt und 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 sitzen, aber die Ringe eins bis sieben unten liegen. Wie kommt Ring sieben, der ja anfangs wie alle anderen Ringe oben liegt, nach unten? Indem Ring sechs oben liegt, während eins bis fünf unten liegen. 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 ist für ungerade Ringzahlen (2**(n+1) - 1)/3, steigt also exponentiell mit der Zahl der Ringe an.
Dabei muss sich der Spieler genau überlegen, welchen Ring er als nächstes 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ärts kommt.
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), 1000 (6), wo sich auf einen Schlag vier Bits oder Ringe ändern. Anders verhalten sich sogenannte Gray-Codes ([6]), die bei jedem Schritt jeweils nur ein 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 [6] in Gray-Code um:
num XOR (num >> 1)Aus der Zahl drei (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 ja bekanntlich (ganz entgegen seiner sonstigen Philosophie "there's one way to do it") drei verschiedenen Verfahren zur String-Formatierung a la printf() an. Listing 1 nutzt die Core-Funktion format(), die Integer mit dem Formatstring "08b" acht Bit breit als Binärzahl mit führenden Nullen ausgibt, weiter die Dezimalzahl i selbst, sowie den daraus mit grayme() generierten Gray-Code.
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 mittels 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, welches es dann als graycode.grayme() nutzen kann. Alternativ kann ein Python-Skript die Funktion mittels from graycode import grayme direkt in ihren Namespace importieren, sodass dort einfach grayme() funktioniert.
 |
| Abbildung 4: Graycodes der Zahlen 1-14 geben die schnellste Transformation der Ringe an. |
Beim Überfliegen der Gray-Codes in Abbildung 4 sieht die Ausgabe tatsächlich 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 bis auf's I-Tüpferl? Ein Testskript soll zur Prüfung durch alle Codes der Reihe nach 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.
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()
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 neunelementige Array mit Indexnummern erscheint. Weiter prüft das Testskript mit der Funktion, wieviele und welche Bits sich von einem Gray-Code zum nächsten verändert haben, und stellt sicher, dass jedes Mal nur ein 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 Eins setzt, die sich verändert haben.
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 Bits 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 anschließend 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 bitweisen Und-Operator:
mask = 1 << bit
num &= ~maskDie nächste Runde der Schleife findet dann eventuell weitere vorhandenen Bits auf den niedrigeren Rängen, bis die untersuchte Zahl den Wert Null annimmt und die Schleife abbricht.
 |
| Abbildung 5: Mittels X-OR stellt das Testskript fest, welche Ringe der User nach dem Gray-Code verschiebt. |
Ob ein vom Gray-Code vorgeschlagener Zug überhaupt 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 2 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. Und für die Ringe drei und höher prüfen Zeilen 39 und folgende mit einer Einsermaske, ob alle rechtsliegenden Ringe unten sind.
Eine Maske mit n rechtsbündigen Einsen erzeugt das etwas seltsam anmutende 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 so von rechts mit Nullen auffüllt, während der Rest der Zahl bei Einser-Bit-Werten verharrt. Ein weiteres Komplement ~ außerhalb der Klammer dreht dann nochmal alle Bits um, sodass die Maske wie gewünscht die ersten n Bits von rechts auf 1 gesetzt hat. Abbildung 6 zeigt die Ausgabe des Testskripts, und verifiziert so, dass der Gray-Code wirklich alle Regeln des Ringspiels einhält und also auch im echten Ringspiel zum Erfolg führt.
 |
| Abbildung 6: 341 Das Testskript überprüft 341 Übergänge nach Gray-Code auf ihre Gültigkeit im Puzzle. |
 |
| Abbildung 7: Nach etwa 250 Zügen, kurz vor der Lösung des Puzzles. |
Das bitweise Verfahren taugt nichts bei größeren Ringzahlen, aber funktioniert bis zur Integergrenze von 32 oder 64 bit, je nach Plattform. Ringspiele mit mehr als 10 Ringen sind aber eh nicht praktikabel, da die Kombinationen zahlenmäßig explodieren. Das Spiel ist ein schöner Zeitvertreib, führt aber bei unsachgemäßer Bedienung nahe an den Nervenzusammenbruch. Es ist wichtig, immer die Züge zum nächsten zu entfernenden Ring vorzuplanen, denn es ist äußerst frustrierend, zurückfahren zu müssen, weil ein Ring, der eigentlich oben bleiben müsste, um einen anderen zu entfernen, im Eifer des Gefechts entfernt wurde und der Spieler nun in den gleichen Fußstapfen zurückmarschieren muss, um das ursprünglich gesteckte Ziel zu erreichen.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2018/05/snapshot/
"Baguenaudier", https://en.wikipedia.org/wiki/Baguenaudier
Video "Baguenaudier Chinese Rings Desperado Centipede puzzles solution and tutorial", https://m.youtube.com/watch?v=qtkvROd1YLY
Martin Gardner, "The Magic and Mystery of Numbers", Scientific American
"Gray Code", Wikipedia, https://en.wikipedia.org/wiki/Gray_code
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc
Unterminated C<...> sequence