Disentis liegt am Rhein, da wo der Fluss noch ganz jung und von hochalpinen Gipfeln umgeben ist. Es ist ein schöner Ort, man kann dort eine alte Benediktinerabtei besichtigen, wandern, nach Gold schürfen und vor allem wunderbar Ski fahren.

Wie kommt man nach Disentis? Am besten nimmt man die Bahn, genauer: die feuerrote Furka-Oberalpbahn, entweder von Chur aus durch das wildromantische Rheintal oder von Andermatt aus über den im Winter verschneiten Oberalppass.

Aus ganz anderer Sicht stellt sich die Titelfrage, wenn man beim Skifahren hoch über Disentis von einem Schlechtwettereinbruch im Restaurant festgehalten wird. Die Bergbahn hat den Betrieb eingestellt, die Talabfahrt ist im Nebel verschwunden und der siebenjährige Sohn mit dem Verzehr von Ovomaltine und Kuchen höchstens fünf Minuten lang ausgelastet. Was tun? Man macht aus der Frage »Wie kommt man nach Disentis?« ein Spiel.

Das geht so: Man greift sich eines der schönen Fotos aus den zahlreich herumliegenden bunten Prospekten und zerschneidet es in 25 quadratische Teile. Diese werden ausgelegt und mit ihrer Bildseite nach unten gedreht (die Rückseiten sind blau). Der Filius darf nun, so oft er mag, eines der blauen verdeckten Teilbilder aussuchen und muss dann sämtliche benachbarten Zettel (bis zu acht Stück) umdrehen – aber nicht den ausgesuchten Zettel selbst. Um dessen Bild sichtbar zu machen, muss er einen blauen Nachbarn zu Hilfe nehmen. Spielziel ist es, das ganze Bild wieder sichtbar zu machen – dann ist man »nach Disentis gekommen«. Unter den umzudrehenden Nachbarn sind häufig auch solche, die eigentlich schon richtig liegen. Deren Bildmotive müssen leider wieder nach unten gedreht werden.

So dauert das Spiel, ganz im Sinne des Erfinders, eine ordentliche Weile. Lange bevor wir damit »nach Disentis gekommen« sind, hat die Seilbahn wieder geöffnet, und die Familie schwebt zufrieden in den eben noch so unerreichbaren Ort hinunter.

Später, der Sohn hat die Sache längst vergessen, plagt den Vater die Neugierde: Wäre es überhaupt möglich gewesen ...? Und falls ja, wie schwierig ist das Spiel? Wie findet man eine Lösung? Gibt es vielleicht mehrere Lösungen? Wie sieht es für andere Zerschnipselungen anstelle von 5x5 aus?

Klar ist zunächst nur: Das letzte blaue Teilstück, wenn man es denn geschafft hat, alle anderen aufzudecken, kann man nicht freilegen. Es hat ja keinen blauen Nachbarn, mit dessen Hilfe man es umdrehen könnte. Na gut, wir erlauben, dass dieses letzte Bild direkt umgedreht wird.

Disentis für Erwachsene

Um mir das lästige Gefummel mit den kleinen Schnipseln zu ersparen, verlegte ich das Spiel auf den Bildschirm eines Computers. Unter der Internet-Adresse http://cs.uni-muenster.de/disentis und mit einem Java-fähigen Browser können Sie es selbst ausprobieren. Beim Start trifft man auf 5x5 quadratische blaue Felder, die beim Anklicken mit der Maus ihre Nachbarfelder zwischen den beiden Zuständen »blau« und »Bild sichtbar« hin- und herschalten. Nur das Anklicken des letzten blauen Felds schaltet dieses selbst um. Die Größe des Spielfelds kann von 2x2 bis 12x12 variiert werden.

Bevor Sie sich an den Rechner setzen, ist eine Warnung angebracht: Nach Disentis gelangt man nicht in ein paar Minuten. Kaum hat man mit dem Spiel angefangen, verliert man sich in der Klickerei, wundert sich, wenn man nach einer halben Stunde noch immer nicht am Ziel ist, freut sich an den Mustern, die man herbeiklicken kann, oder daran, dass man alle Felder bisauf gerade mal zwei blaue aufgedeckt hat, und ärgert sich zugleich, weil der Weg von zwei blauen Feldern zu einem einzigen allem Anschein nach nicht kürzer ist als der von 25 zu einem. Nein, es ist keineswegs ­einfach, nach Disentis zu kommen. (Es sei denn, man stellt eine Spielfeldgröße von 2 oder 3 ein. Dann geht alles wie von selbst.)

Im Bild auf Seite 110 unten kann man einen Spielverlauf sehen, der auf direktem Weg zu einer Situation mit nur noch zwei blauen Feldern führt. Probieren Sie, ob Sie von dieser Situation aus schneller ans Ziel gelangen als von der ursprünglichen!

Einige regelmäßige Konfigurationen sind tatsächlich leicht zu erreichen. Zum Beispiel erhält man mit nur fünf Klicks (in die Mitte und die vier Ecken) ein Schachbrettmuster.

Mit dem umgekehrten Schachbrett, bei dem die Ecken aufgedeckt sind, tut man sich allerdings erheblich schwerer. Richtig frustrierend wird die Sache jedoch dann, wenn man nach langem Herumklicken plötzlich durch Zufall das letzte blaue Feld vor sich hat. Man klickt es an, das ganze Bild ist da, man ist sozusagen in Disentis angelangt – und hat den Weg vergessen. Noch immer hat man keine Ahnung, wie man nach Disentis kommt.

Wenn man sein Ziel nicht auf direktem Weg erreichen kann, hilft manchmal ein Umweg weiter – in unserem Fall über Trisentis. Auf der Landkarte der Schweiz sucht man vergebens nach diesem Namen; er steht für eine etwas trivialere Variante des Disentis-Spiels, bei der es erlaubt ist, jedes beliebige Feld anzuwählen und damit dessen Nachbarfelder zwischen den zwei Zuständen »verdeckt« und »sichtbar« hin- und herzuschalten. Damit hat man viel mehr Einflussmöglichkeiten als bei der ursprünglichen Version. Auch die gesonderte Behandlung, die wir dem letzten verdeckten Feld geben mussten, erübrigt sich.

Trisentis: der Umweg zum Ziel

Trisentis kann man ebenfalls auf der oben angegebenen Website ausprobieren. Zur Unterscheidung von Disentis werden aufgedeckte Karten als gelbe Quadrate dargestellt. Spielziel ist also, ein völlig gelbes Spielfeld herzustellen.

Für Trisentis der Größe 6x6 hat Ludger Sasse vom Institut für Physiologie der Universität Münster eine Art Gameboy gebaut, den Kinder gerne und mit erstaunlicher Ausdauer benutzen. An die Stelle der Papierschnipsel treten Schalter mit eingebauter Leuchtdiode. Wenn ein Feld leuchtet, entspricht das dem Zustand »sichtbar«. Drücken auf einen Schalter ändert den Beleuchtungszustand (an oder aus) aller Nachbarfelder. Die Schaltung ist im Prinzip sehr einfach. Durch Ausblenden von Schaltern mit einer Maske kann man damit auch kleinere Spielfeldgrößen realisieren, beispielsweise 4x4 durch Zudecken der Randzeilen.

Das Trisentis-Spiel der Größe 4x4 ist wirklich kinderleicht zu lösen. Sechs Klicks genügen, um alle Felder gelb zu machen . Und wie man durch Experimentieren sehr schnell feststellt, kommt es auf die Reihenfolge der Klicks überhaupt nicht an. Man kann unterwegs auch beliebige andere Felder anklicken und den Effekt später durch nochmaliges Anklicken wieder rückgängig machen. Für den Endzustand ist nur wichtig, ob die Anzahl der Klicks auf ein Feld ungerade oder gerade war.

Für das Spiel Disentis gilt im Prinzip dasselbe. Es kommt nicht darauf an, ob man drei Felder in der Reihenfolge A, B, C oder C, B, A anwählt – es sei denn, Feld A wäre durch die Aktion B bereits umgedreht worden und daher nicht mehr anwählbar. Aus diesem Grund ist Disentis schwieriger zu spielen als Trisentis.

Das Wesentliche eines Trisentis-Spielverlaufs wird offenbar durch ein Quadrat aus Nullen und Einsen beschrieben, bei der die Einsen die Felder angeben, die anzuklicken sind. Im vorangehenden Beispiel ist das

Die Mathematiker nennen eine solche Tabelle eine Matrix und umgeben sie mit Klammern, statt die einzelnen Felder einzufärben. Eine Matrix auf einen Zustand anzuwenden bedeutet genau die Felder anzuklicken, in denen eine Eins steht.

Die Matrix unseres Beispiels kann man an der Senkrechten oder an einer ihrer Diagonalen spiegeln, die Wirkung bleibt dieselbe. Was passiert, wenn man zunächst die Matrix und dann eine ihrer gespiegelten Varianten auf den Ausgangszustand anwendet? Dann werden alle Felder zweimal umgeklappt, und das Spiel ist wieder im Urzustand.

Statt die beiden Matrizen hintereinander anzuwenden, kann man sie auch addieren und die Matrix, die sich daraus ergibt, anwenden. Dabei ist die Addition elementweise zu verstehen: Das linke obere Element der einen Matrix plus das linke obere Element der zweiten Matrix ergibt das linke obere Element der Summenmatrix, und so weiter. Vor allem aber: 1+1=0, denn zweimal dasselbe Feld anzuklicken ist dasselbe wie nichts tun.

In der Tat lässt diese Matrix jeden Zustand, auf den sie angewendet wird, unverändert. Addiert man nun noch eine weitere der gespiegelten Matrizen dazu, dann wechseln wieder alle Felder ihre Farbe. Man bekommt eine neue, von der ersten wesentlich verschiedene Lösung.

Man kann das durch Anklicken der entsprechenden zehn Felder bestätigen, aber schon durch Hinschauen kann man sich davon überzeugen, dass in der letzten Matrix jedes der 16 Felder eine ungerade ­Anzahl von Einsen als Nachbarn hat. Und das ist genau die Eigenschaft, die eine solche Matrix zu einer Lösung von Trisentis macht.

Wer zwei Semester Mathematik studiert hat, nickt an dieser Stelle und stellt fest, dass hinter dem Ganzen offenbar ein Stück Lineare Algebra über dem Körper F 2 steckt. Lineare Algebra ist – unter anderem – die Wissenschaft von der Auflösung linearer Gleichungssysteme mit beliebig vielen Unbekannten; erste Anfänge davon pflegt man in der Schule unter den Namen »Einsetzungsverfahren« und »Additionsverfahren« kennen zu lernen. Hier rechnen wir allerdings nicht mit den gewöhnlichen (reellen) Zahlen, sondern mit einem Zahlensystem, das nur aus 0 und 1 besteht. Die Rechenregel 1+1=0 ist etwas gewöhnungsbedürftig; aber die Gesetze der Addition und der Multiplikation gelten »wie zu Hause«, und alle Rechenoperationen – mit der üblichen Ausnahme der Division durch null – sind durchführbar. Die Sätze aus der Linearen Algebra hängen nicht an den Eigenschaften der reellen Zahlen, sondern nur an diesen formalen Rechengesetzen; deswegen sind sie unverändert auf unser Spiel anwendbar.

Wie man nach Trisentis kommt

Für Trisentis der Größe n sind n 2 lineare Gleichungen mit ebenso vielen Unbekannten zu lösen. Mit Computerunterstützung ist diese Berechnung für nicht allzu große n kein Problem. Unsere Klick-Matrix ist übrigens nicht die Matrix dieses Gleichungssystems! Vielmehr ist sie als der – zunächst unbekannte – Vektor der Länge n 2 aufzufassen, der das Gleichungssystem löst.

Für ein Urlaubsspiel ist dieser Zugang aber eigentlich nicht das Wahre. Glücklicherweise gibt es auch einen Weg, der ganz ohne Rechnen zum Ziel führt und zudem unterwegs manchen Ausblick bietet, den man bei der Reise mit dem Hochgeschwindigkeitszug Computer gar nicht wahrnehmen würde. Man kann aus jeder Konfiguration heraus jede andere ansteuern, wenn man den folgenden Zeilenalgorithmus kennt.

Um die Felder einer Zeile in einen gewünschten Zustand zu bringen (zum Beispiel alle gelb), besucht man von links nach rechts alle Felder der darunter liegenden Zeile, beginnend mit dem zweiten Feld. Immer dann, wenn das schräg links über dem gerade besuchten Feld liegende Feld die falsche Farbe hat, klickt man und gibt ihm so die richtige Farbe.

Auf diese Weise kann man die Felder einer Zeile mit Ausnahme des letzten Felds in den gewünschten Zustand bringen. Weil man von schräg unten klickt und nach rechts fortfährt, machen die weiteren Eingaben nichts mehr kaputt. Wenn das letzte Feld der oberen Zeile nun auch die richtige Farbe hat, ist diese Zeile »fertig«. Andernfalls klickt man das erste Feld der unteren Zeile an, das man noch nicht berührt hatte, und durchläuft die Zeile ein zweites Mal, wobei man wieder die schräg links darüber liegenden Farben nach Bedarf korrigiert.

Nur die unterste Zeile des Spielfelds kann man auf diese Weise nicht aufräumen – zu ihr gibt es keine darunter liegende Zeile. Außerdem funktioniert das Verfahren nur dann mit Sicherheit, wenn die Zeilenlänge n bei Teilung durch 3 den Rest 0 oder 1 hat. Wenn n den Rest 2 hat, kann es vorkommen, dass auch nach dem zweiten Durchgang die darüber liegende Zeile im letzten Feld wieder die falsche Farbe hat. (Das liegt daran, dass jedes innere Feld der unteren Zeile zu drei Feldern der oberen Zeile benachbart ist, während die beiden Randfelder nur zwei Nachbarn in der oberen Zeile haben.)

Am besten übt man das Verfahren mit einem 6x6-Spielfeld. Nach kurzer Zeit beherrscht man die Regel und kann dann auch ein völlig durcheinander gebrachtes Spiel in jede gewünschte Konfiguration (blau, gelb, Schachbrett, ...) bringen – mit Ausnahme der letzten Zeile.

Wie kann man die auch noch in Ordnung bringen? Durch Klicken in die bisher ungenutzte oberste Zeile des Spielfelds. Aber welche Felder genau sind anzuwählen? Das findet man durch gezieltes Probieren heraus. Von einem einheitlich blauen Spielfeld ausgehend klickt man in der ersten Zeile ein einzelnes Feld an und färbt dann mit dem Zeilenalgorithmus das ganze Spielfeld blau, bis in der letzten Zeile gelbe Felder übrig bleiben. Beim 6x6-Trisentis ergibt die Eingabe in Zeile 1 (also das Anklicken von Feld 1) den Zustand in der sechsten Zeile, weil die Felder 2, 3 und 4 gelb bleiben. Auf dieselbe Weise findet man die Wirkung einer Eins an anderen Stellen der ersten Zeile:

Jetzt kann man kombinieren: Die Eingabe (Natürlich wird dabei wieder mit 1+1=0 gerechnet.).

Aha! Man kann den Zustand eines einzelnen Felds der letzten Reihe ändern. Das gilt für alle Felder der letzten Zeile, wie man durch Probieren herausfindet. Die folgende Tabelle zeigt, wie jedes Feld der letzten Zeile einzeln zu beeinflussen ist:

Damit wissen wir, wie man »nach Trisentis kommt«: Ein erster Durchgang mit dem Zeilenalgorithmus dreht alle Felder auf die gelbe Seite bis auf möglicherweise einige Felder in der untersten Reihe. Man sieht nach, welche das sind, addiert die zugehörigen Eingaben für die erste Zeile, klickt diese Felder an und macht einen zweiten Durchgang mit dem Zeilenalgorithmus. Und da passiert das Wunder: Das Spiel geht auf, auch die letzte Zeile wird gelb.

Nicht für alle n kann man das Spiel auf diese Weise lösen. So gibt es für alle ungeraden n Konfigurationen des Spielfelds, die nicht erreichbar sind, darunter das gelbe Spielfeld – Trisentis ist nur für gerade n lösbar! Auch bei geradem n kann man nicht immer alle Konfigurationen herbeiklicken, mindestens bis n = 150 ist aber für gerades n »gelb« immer möglich.

Für manche Werte von n gibt es genau eine Lösung, die dann in der Regel eine schöne Symmetrie besitzt, für andere dagegen sehr viele, meist weniger schöne. Im Bild Seite 112 sieht man drei Beispiele für dieses Verhalten.

Das Spiel Trisentis gibt Anlass zu mancherlei Entdeckungen – weit mehr als nur die, die hier erwähnt wurden. Aber wie kommt man denn nun von Trisentis nach Disentis, sprich zur Lösung des ursprüng­lichen Problems? Einen markierten Weg, also eine Vorschrift wie den Zeilenalgorithmus für Trisentis, gibt es zwar bisher nicht. Das Ziel liegt aber in greifbarer Nähe, und man kommt ganz gut querfeldein – ohne einen algorithmischen Weg – durch.

Was ist zu tun? Man löse zunächst das Trisentis-Spiel der entsprechenden Größe, und zwar so, dass ein einzelnes blaues Quadrat übrigbleibt (das Feld, das sich beim letzten Klick selbst umdreht). Die Eingaben für diese Lösung versucht man dann in eine solche Reihenfolge zu bringen, dass jeder Klick in ein blaues Feld erfolgt. Man darf zusätzlich Klicks in Felder machen, die nicht in der Trisentis-Lösung auftauchen, muss diese aber später rückgängig machen. Genauer gesagt: Andere Felder müssen eine gerade Anzahl von Malen angeklickt werden – am besten null Mal.

Für die Reihenfolge der anzuklickenden Felder kommt man mit der einfachsten denkbaren Lösung schon relativ weit: Man gehe zeilenweise vor. Ist eines der Eingabefelder nicht blau, überspringt man es und holt die verpasste Eingabe nach, sobald es durch andere Eingaben blau wird. Wenn kein Eingabefeld mehr blau ist, klcike man ein Hilfsfeld an – am besten ein benachbartes, sodass das eigentlich zu klickende Feld blau wird – und widerrufe diesen Klick später durch einen Klick auf dasselbe Feld. So findet man zum Beispiel die im Bild unten angegebene Lösung.

Aber die Furka-Oberalp-Bahn hält doch in der Ortsmitte von Disentis! Wäre es nicht schön, wenn wir dort aussteigen könnten? Für uns bedeutet das, eine Folge von Eingaben zu konstruieren, bei der das mittlere Quadrat des Spielfelds als letztes übrigbleibt. Das geht tatsächlich, sogar in weniger als zwanzig Schritten. Finden Sie den Weg? Die Lösung finden Sie auf unserer Website.

Aus: Spektrum der Wissenschaft 1 / 2003, Seite 110
© Spektrum der Wissenschaft Verlagsgesellschaft mbH