Mathematik:Neun Ziffern gegen einen

Europa ist der Faszination des japanischen Zahlenrätsels Sudoku verfallen - die höhere Mathematik dahinter erahnen die meisten Spieler nur.

Wolfgang Blum

Es scheint eine Sucht zu sein. Die Abhängigen sind überall zu sehen. In Büros, Klassenzimmern, U-Bahnen, Flugzeugen - immer ist es das gleiche Bild.

Mathematik: Die Macht der Zahlen - Sudoku.

Die Macht der Zahlen - Sudoku.

Menschen sitzen da, mit Stiften in der Hand, beugen sich über Zettel mit Kästchen und Zahlen darauf, murmeln, fahren senkrecht und waagrecht über die Blätter, als steuere sie eine geheime Macht. Das Phänomen hat einen Namen: Sudoku.

Wie bei vielen kniffligen Spielen und Rätseln sind die Regeln einfach: In ein Schema aus neun mal neun Kästchen sollen die Ziffern Eins bis Neun so eingetragen werden, dass in jeder Zeile und in jeder Spalte jede Ziffer genau einmal vorkommt.

Logisches Denken, Konzentration und eine Schwäche für Ordnung

Zudem sind die 81 Kästchen in neun quadratische Blöcke aufgeteilt. Auch in diesen Blöcken soll jede Ziffer genau einmal stehen. Zu Beginn sind bereits einige Zahlen in das Gitter eingetragen. Der Rätsellöser soll die anderen gemäß den Regeln finden und einsetzen.

Geübte Sudokisten schaffen leichte bis mittelschwere Rätsel in einer Viertelstunde, manchmal aber dauert es Stunden, bis das Gitter gefüllt ist. Spötter sagen, die Zahlenrätsel seien ein Spiegel unserer Zeit. Sie zu lösen, verlange weder Bildung, Kultur noch Sprache.

"Alles, was man braucht, ist logisches Denken, Konzentration und eine Schwäche für Ordnung", bestätigt der Schweizer Stefan Berner, einer von 84 Teilnehmern aus 22 Ländern an der ersten Sudoku-Weltmeisterschaft, die im März 2006 im italienischen Lucca ausgetragen wurde.

Gewonnen hat dort Jana Tylova, eine 31-jährige Buchhalterin aus Tschechien, die eigenen Angaben zufolge täglich etwa zwei Stunden trainiert. Die vier deutschen Teilnehmer belegten nur hintere Plätze. Erstaunlicherweise finden sich unter den Sudoku-Fans viele Menschen, die Mathematik in der Schule nie gemocht haben und immer noch eine ausgeprägte Ablehnung dem Fach gegenüber pflegen.

Wie Diskussionen im Internet belegen, scheinen sie zu glauben, Sudokus verhielten sich zur Mathematik wie Buchstabensuppe zu Goethes "Faust". Freilich sind die verbreiteten 9-mal-9-Rätsel nicht die Speerspitze der Forschung, aber wer das Problem verallgemeinert, kommt schnell bei den schwersten Problemen an, die die Mathematik zu bieten hat.

Und auch zur Lösung ganz normaler Sudokus sind mathematische Fertigkeiten gefragt: strikt logisches Vorgehen, Kombinieren von Sachverhalten, langes Grübeln, bis einem die Lösung vor Augen steht.

Erst Sudokus haben die Deutschen verführt, mathematisch zu denken

"Der Gedanke, Sudokus hätten nichts mit Mathematik zu tun, ist abstrus", sagt Thorsten Koch vom Konrad-Zuse-Zentrum für Informationstechnik in Berlin. Koch hat ein Computerprogramm für die Zahlenrätsel geschrieben. Selbst löst er keine.

Schließlich beschäftige er sich schon beruflich zur Genüge mit Mathematik, sagt er. "Sudoku ist angewandte Logik, die wir im normalen Leben fast nie einsetzen können", argumentiert Wayne Gould, der die in Japan seit Langem populären Rätsel auch im Westen eingeführt hat.

Sudokus befriedigten ein urmenschliches Grundbedürfnis, nämlich durch Nachdenken Ordnung ins Chaos zu bringen. Eigenen Angaben zufolge löst der pensionierte Strafrichter Gould täglich ein Sudoku. Albrecht Beutelspacher grübelt hingegen nur gelegentlich über einem. Dennoch wundert es den Mathematikprofessor von der Universität Gießen nicht, dass sich so viele damit beschäftigen.

"Die Menschen haben Spaß daran zu denken", ist der Gießener überzeugt, der zugleich das dortige Mathematikmuseum leitet. Ihm stelle sich weniger die Frage, warum das Zahlenrätsel so beliebt ist, sondern vielmehr, warum die Mathematik so unbeliebt ist. Denn auch sie habe sehr viel mit Denken zu tun: "Aber das wird in der Schule nicht vermittelt."

Erst das Lösen von Sudokus hat die Deutschen nachhaltig dazu verführt, mathematisch zu denken. Die Verlockung ist hierzulande erst seit wenigen Monaten verbreitet; sie hat ihre Opfer über London, Hongkong, Tokio und New York erreicht.

Neun Ziffern gegen einen

Doch die Wurzeln des Zahlenrätsels sind viel älter. Bereits im Alten Rom tauchten seine Vorläufer auf: sogenannte lateinische Quadrate, Zahlenfelder, bei denen in jeder Zeile und jeder Spalte jede Ziffer nur einmal auftaucht. Lateinische Quadrate sind nicht immer neun mal neun Felder groß und auch nicht in neun kleinere quadratische Blöcke aufgeteilt wie Sudokus. Im abergläubischen Mittelalter erfreuten sich die magischen Quadrate großer Beliebtheit.

Frühere Formen von Sudoku

Bei ihnen addierten sich die Zeilen, Spalten und Diagonalen jeweils zur selben Summe. In Albrecht Dürers Kupferstich "Melencolia I" zum Beispiel zu 34. Auch die vier Eckfelder ergeben 34, ebenso die Felder in der Mitte; die mittleren beiden Felder der linken und der rechten Spalte zusammen ergeben 34, desgleichen die mittleren beiden der obersten und der untersten Zeile.

Und unten in der Mitte steht 1514, das Jahr, in dem Dürer den Stich anfertigte. So hohe Ansprüche gelten für Sudokus nicht. Doch ranken sich um die Zahlenrätsel eine ganze Reihe Probleme der praktischen Mathematik. Sie beginnen mit der Frage: Sind eines nicht allzu fernen Tages nicht alle Sudokus der Welt gemeistert?

Schon der Schweizer Mathematiker Leonhard Euler überlegte vor 250 Jahren, wie viele verschiedene lateinische Quadrate es wohl gibt. So sind zwei verschiedene 2-mal-2-Quadrate denkbar, in denen die Eins und die Zwei in jeder Zeile und jeder Spalte genau einmal vorkommen. Zwölf Möglichkeiten ersann Euler für lateinische 3-mal-3-Quadrate, 576 für solche mit 4-mal-4-Feldern.

Doch eine allgemeingültige Formel konnte Euler nicht finden. Die ermittelte erst im Jahr 1979 der Mathematiker James Nechvatal in seiner Dissertation in San Diego. Allerdings ist sie ziemlich kompliziert. Lateinische 9-mal-9-Quadrate gibt es demnach unvorstellbar viele: 5 524 751 496 156 892 842 531 225 600 - mehr als fünf Quadrilliarden.

Betrachtet man allerdings, wie es die Fachwelt hält, lateinische Quadrate als gleich, wenn sie sich nur durch Spiegeln, Drehen, das Vertauschen von Zeilen oder Spalten oder durch den Austausch von kleinen Zifferngruppen unterscheiden, schrumpft die Anzahl der 9-mal-9-Gitter auf einige hundert Billiarden: 377 597 570 964 258 816.

Hunderttausend Jahre, um sie alle zu lösen

Nun ergibt aber nicht jedes lateinische Quadrat ein Sudoku. Schließlich muss ja zusätzlich in jedem Block jede Ziffer genau einmal auftreten. Bertram Felgenhauer von der Technischen Universität Dresden und Frazer Jarvis von der Universität im englischen Sheffield haben im Jahr 2005 durch mathematisches Knobeln und systematische Suche mit dem Computer herausgefunden, dass es mehr als sechs Trilliarden verschiedene ausgefüllte Sudokus gibt.

Etwas mehr als jedes Millionste lateinische Quadrat erfüllt demnach zugleich die Bedingung für die Blöcke. Zählt man wieder nur die Zahlenanordnungen als wesentlich verschieden, die nicht durch Drehen, Spiegeln, einen Austausch von Zifferngruppen, Zeilen oder Spalten ineinander übergehen, reduziert sich die Zahl noch mal gewaltig: auf 5.472.730.538 - gut fünf Milliarden.

Zeilen und Spalten dürfen dabei entweder nur innerhalb eines Blocks vertauscht werden oder als Dreierpakete, die jeweils einen Block ausmachen. Und zwei Ziffern kann man austauschen, wenn sie diagonal angeordnet die Ecken eines Rechtecks ausmachen.

Es gibt also mehr Menschen auf der Erde als unterschiedliche Sudokus. Das ist allerdings kein Grund zur Panik. Denn erstens bräuchte man, wenn man nur zehn Minuten pro Rätsel ansetzt und ununterbrochen Tag und Nacht tüftelte, immer noch knapp hunderttausend Jahre, um alle zu lösen.

Und zweitens haben Felgenhauer und Jarvis nur vollständig ausgefüllte Sudokus gezählt.

Zu jeder solchen Lösung lassen sich aber mehrere Aufgabenstellungen konstruieren, indem Zahlen einfach ausradiert werden. Die einzige Regel dabei lautet: Die angegebenen Ziffern dürfen lediglich eine Lösung zulassen. Jede Zahl im ausgefüllten Tableau muss eindeutig festgelegt sein.

Neun Ziffern gegen einen

Üblicherweise ist ungefähr ein Drittel der Ziffern vorgegeben. Doch sind 36.000 Rätsel bekannt, bei denen nur 17 Zahlen in den Kästchen stehen, wie Gordon Royle von der University of Western Australia gezählt hat. Ein Sudoku mit eindeutiger Lösung und nur 16 vorgegebenen Ziffern hat bis heute kein mathematischer Laie und auch kein Profi wie Royle gefunden.

Sudoku-Kategorien: leicht, mittel, schwer, teuflisch

Wer danach sucht, kann verschiedene Vorgaben ausprobieren oder er versucht, das Problem mit mathematischer Finesse zu lösen. Jedenfalls hat noch niemand bewiesen, dass es so etwas nicht geben kann.

Die umgekehrte Frage, wie viele Ziffern vorgegeben sein können, ohne dass es eine eindeutig festgelegte Lösung gibt, ist dagegen beantwortet: 77 der 81. Sind höchstens drei frei, gibt es - wenn überhaupt - nur eine Ergänzung, die den Regeln entspricht. Denn bei drei unausgefüllten Kästchen ist mindestens eines das einzige leere in seiner Zeile oder Spalte. Damit ist sein Inhalt klar.

Und die beiden verbleibenden bilden dann ebenfalls die einzigen Lücken ihrer Zeilen oder Spalten. Beispiele für Zahlengitter mit 77 vorgegebenen Ziffern, die zu keiner eindeutigen Lösung führen, sind relativ einfach zu konstruieren.

Fehlen bei einem ausgefüllten Sudoku in den ersten beiden Einträgen der ersten und der vierten Zeile die gleichen Ziffern, lassen sie sich auf zwei Arten platzieren, ohne dass die Regeln verletzt werden. Sudoku-Bücher bieten meist verschiedene Kategorien: leicht, mittel, schwer, teuflisch.

Der Schwierigkeitsgrad eines Rätsels hängt allerdings nicht allein von der Anzahl der vorgegebenen Ziffern ab. Genau definieren lässt er sich sowieso nicht, da es auf die Vorlieben jedes Knoblers ankommt.

Je nachdem wie er vorgeht, wird er diese oder jene Aufgabe als besonders schwierig empfinden. Dennoch ergeben die Einstufungen Sinn, da sich die meisten Rater mit ähnlichen Überlegungen durch die Aufgabe kämpfen. Für Computer stellen Sudokus eine eher leichte Übung dar. Das einfachste Programm prüft stumpf eine Ziffernkombination nach der anderen, bis es eine gültige findet.

Die Methode Ariadne-Faden

Der Rechner fängt dabei mit dem ersten freien Feld an und trägt versuchsweise eine Eins ein. Führt das nicht sofort auf zwei Einser in einer Zeile, einer Spalte oder einem Block, wird im nächsten freien Feld wieder eine Eins notiert. Stößt der Computer irgendwann auf einen Widerspruch, setzt er die zuletzt gewählte Zahl eins höher und probiert von da ab aus, ob jetzt alles stimmt.

Ist er bei neun angelangt und es klappt immer noch nicht, geht der Rechner einen Schritt zurück und erhöht die vorletzte gewählte Ziffer um eins. Nach diesem Schema werden systematisch alle möglichen Zahlenkombinationen durchprobiert. Geht das Sudoku auf, finden sich so irgendwann Ziffern, die keine der Regeln verletzen.

Sudokulogen haben die Methode Ariadne-Faden getauft, weil der Rechner wie Theseus im Labyrinth den eingeschlagenen Weg immer wieder zurückverfolgt. Mit diesem Hilfsmittel lassen sich auch Sudoku-Rätsel erstellen. Der Programmierer fängt mit ein paar Ziffern an, die in ein 9-mal-9-Gitter geschrieben sind.

Stößt der Computer auf eine Regelverletzung, löscht der Programmierer eine der vorgegebenen Ziffern und lässt den Rechner das Gitter mit den verbleibenden als Startangabe prüfen.

Womöglich findet der Rechner aber auch heraus, dass die Vorgabe mehrdeutig ist. Dazu muss er nach der ersten gefundenen Lösung in ursprünglich freie Felder höhere Zahlen einsetzen: Ist in der ersten Lösung das erste freie Feld mit einer Drei belegt, setzt der Rechner dort eine Vier und probiert an der zweiten Stelle wieder eine Eins und so weiter, bis er vielleicht feststellt: Mit der Vier geht es nicht.

Der Rechenaufwand ist zwar um ein Vielfaches höher als bei der ersten Lösung, aber für Computer problemlos zu bewältigen. Erst wenn der Ariadne-Faden zu einer eindeutigen Lösung führt, ist ein neues Rätsel gefunden. Für menschliche Gehirne ist der Ariadne-Faden denkbar ungeeignet.

"Der Computer braucht nur Bruchteile einer Sekunde"

Jedes Mal, wenn ein Fehler auftaucht, und das passiert normalerweise Tausende von Malen, muss der Rater zurückgehen und von dort neu anfangen. Sudoku-Fans wenden die Methode deswegen nur im äußersten Notfall an, wenn sie sich sonst gar nicht mehr zu helfen wissen. Andere Programme zum Lösen von Sudokus setzen auf Methoden, die menschlichen Zahlenakrobaten eher entgegenkommen.

Volker Kaibel und Thorsten Koch vom Konrad-Zuse-Zentrum für Informationstechnik in Berlin haben das Zahlenrätsel dagegen in ein Problem der ganzzahligen Optimierung übersetzt. Dazu basteln sie aus einem Sudoku ein Gleichungssystem mit vielen hundert Variablen, die jeweils die Werte null oder eins annehmen dürfen.

Pro freiem Feld werden neun Unbekannte eingeführt, von denen nur eine die Eins sein darf. Ist zum Beispiel die sechste Unbekannte für ein Feld die Eins, so bedeutet das: An diese Stelle kommt eine Sechs. In den insgesamt 324 Gleichungen, die für ein Sudoku erfüllt sein müssen, werden nur Unbekannte addiert. Dabei muss jedes Mal eine Eins herauskommen.

Um solche einfachen Gleichungssysteme zu lösen, haben Wissenschaftler in den vergangenen Jahrzehnten effiziente Lösungsverfahren entwickelt. "Wir haben mittlerweile 15 000 Sudokus gerechnet", berichtet Koch stolz: "Für ein Rätsel braucht der Computer nur Bruchteile einer Sekunde." Neben den Knobelaufgaben übersetzen die Berliner Forscher viele andere kombinatorische Probleme in Gleichungen.

So erstellen sie zum Beispiel Fahrpläne oder helfen, Chips zu konstruieren und Mobilfunkstationen so zu platzieren, dass möglichst wenige für ein Netz reichen - die Methode ist dem Lösen der Zahlenrätsel jeweils sehr ähnlich. So, wie die Berliner Sudokus in Gleichungen verwandelt haben, gehen Mathematiker gerne vor.

Sie formulieren eine Aufgabe um, decken damit Querverbindungen zwischen verschiedenen Teildisziplinen auf und finden dadurch häufig unerwartete Lösungen. Sudokus lassen sich auch als Problem der Graphentheorie auffassen. Ein Graph besteht dabei aus Verzweigungspunkten, den Knoten, und Verbindungen zwischen ihnen, den Kanten.

Die teuflischen Varianten

Ein Sudoku-Graph hat für jedes der 81 Felder einen Knoten. Zwei Knoten sind immer dann über eine Kante verbunden, wenn die zugehörigen Kästchen in einer Zeile, einer Spalte oder in einem Block lie Lösungsvergen. Von jedem Knoten gehen somit 20 Kanten aus (acht für die Spalte, acht für die Zeile und vier für die verbleibenden Kästchen im Block).

Da jede Kante an zwei Knoten anliegt, hat der Graph insgesamt 81 mal 20 geteilt durch zwei Kanten, also 810. Statt Ziffern stehen neun verschiedene Farben zur Verfügung. Knoten, die zu bereits belegten Sudoku- Feldern gehören, sind entsprechend eingefärbt.

Ziel ist es nun, die restlichen Knoten so zu färben, dass jeweils zwei, die über eine Kante verbunden sind, verschiedenfarbig sind. Da Mathematiker die Graphentheorie im Gegensatz zu Sudokus bereits seit Jahrhunderten erforschen, könnte sich die Querverbindung als fruchtbar erweisen.

Vielleicht gelingt so eines Tages der Nachweis, dass 16 vorgegebene Ziffern nicht reichen, um ein Zahlenrätsel eindeutig zu machen. Rätselfreunde, die sich unterfordert fühlen, können sich auch Knobeleien mit leicht unterschiedlichen Regeln zuwenden: Mal ist vorgegeben, auf welchen Feldern nur ungerade Ziffern stehen dürfen, mal spielen wie beim "Killer-Sudoku" die Summen bestimmter Zahlen eine Rolle, dann wiederum besteht das Ratefeld aus mehreren 9-mal-9-Tableaus, die sich zum Beispiel um einen Block an der Ecke überlappen.

Zudem lässt sich das Gitter größer gestalten. Bedingung ist nur, dass die Seitenlänge eine Quadratzahl darstellt, damit quadratische Blöcke gebildet werden können, die genauso viele Kästchen haben wie eine Zeile oder eine Spalte. Statt eines 9-mal-9-Gitters ließe sich auch ein 16- mal-16-Gitter bearbeiten.

Es bestünde aus 16 Blöcken zu je vier mal vier Kästchen und wäre eben mit 16 verschiedenen Symbolen zu füllen, zum Beispiel mit den Zahlen von eins bis 16 oder den Buchstaben von A bis P. Allerdings hat das Rätsel dann 256 Kästchen und wird dadurch etwas unübersichtlich. Zumindest Mathematiker brüten auch über Sudokus im Maßstab 16 mal 16, 25 mal 25, 36 mal 36 und so weiter.

Carla Gomes von der Cornell University in Ithaca bei New York und ihre Mitarbeiter haben viele der Zahlenrätsel am Computer gelöst und dabei entdeckt, dass sich bei gleicher Größe viele Gitter schnell füllten, während sich andere als äußerst vertrackt erwiesen.

Der Knackpunkt bei ihnen war, an welcher Stelle der Rechner begonnen hatte, Ziffern einzufügen. Gomes verfolgte daher die Idee, das Programm immer dann abzubrechen, wenn es zu lange dauerte, um es dann an einer anderen Stelle des Sudokus neu zu starten - in der Hoffnung, einen günstigeren Startpunkt zu erwischen. Nun will die Wissenschaftlerin ihre Software verbessern, indem sie sich von menschlichen Sudoku-Lösern abschaut, wie diese Regeln und Muster kombinieren, um einen günstigen Startplatz zu finden.

Die beiden Japaner Takayuki Yato und Takahiro Seta untersuchten sogar Sudokus beliebiger Größe, das heißt, Gitter mit n2 mal n2 Ziffern, wobei n für jede beliebige positive ganze Zahl steht. Kürzlich konnten sie beweisen, dass n2-mal-n2-Sudokus ein NP-vollständiges Problem darstellen.

NP heißt, dass es leicht zu beschreiben ist. Aber bei größeren n kann die Rechenzeit zur Lösung des Rätsels förmlich explodieren. Vollständig wiederum bedeutet: Fände ein schlauer Kopf doch ein effizientes Programm für n2-mal-n2-Sudokus, könnte er damit gleichzeitig viele andere wichtige mathematische Problemstellungen bewältigen; die Fragen ließen sich ineinander übersetzen.

Dem Entdecker wäre damit nicht nur der Ruhm der Fachwelt sicher, sondern auch ein Preis von einer Million Dollar. Den hat das Clay Mathematics Institute darauf ausgeschrieben, ein NP-vollständiges Problem in vertretbarer Rechenzeit zu lösen oder zu beweisen, dass es nicht möglich ist.

Sudokus stellen demnach selbst die besten Mathematiker der Welt vor eine Aufgabe, die sie nicht meistern konnten. Vielleicht ist das ein schwacher Trost für Normalsterbliche, die manchmal schier daran verzweifeln, ein paar richtige Ziffern zu finden.

Zur SZ-Startseite
Jetzt entdecken

Gutscheine: