Süddeutsche Zeitung

Sudoku:Die Suche nach der kniffligsten Kombination

Sudoku unterhält Millionen rund um den Globus - aber die Mathematik dahinter ist auch für Wissenschaftler eine Herausforderung.

Wolfgang Blum

Millionen Menschen rund um den Globus knobeln an Sudokus, um sich in der Freizeit zu entspannen. Deutlich weniger tun es aus beruflichen Gründen.

Neben den Autoren der Aufgaben sind auch Mathematiker darunter, denn die Zahlenrätsel werfen schwierige mathematische Fragen auf - zum Beispiel, wie das denkbar schwierigste Rätsel aussehen müsste.

Manche der Fragen haben die kanadischen Mathematiker Agnes Herzberg und Ram Murty kürzlich in einem Artikel für die Zeitschrift Notices of the American Mathematical Society geklärt (1).

Bei Sudokus geht es darum, die Ziffern eins bis neun so in ein Schema aus neun mal neun Kästchen einzutragen, dass in jeder Spalte und in jeder Zeile jede Ziffer genau einmal vorkommt.

Zudem muss jede Ziffer einmal in jedem der neun Blöcke zu drei mal drei Kästchen stehen. Als Vorgabe sind einige Kästchen bereits zu Anfang ausgefüllt - und zwar so, dass es nur eine mögliche Vervollständigung des Tableaus gibt.

40.731 verschiedene Rätsel

Wie viele Felder mindestens vorgegeben sein müssen, um eine eindeutige Lösung vorzugeben, haben Mathematiker bis heute nicht herausgefunden. Gordon Royle von der Universität von West-Australien hat sich auf Sudokus mit 17 bereits eingetragenen Ziffern spezialisiert. Aktueller Stand: 40.731 verschiedene Rätsel (2). Ob indes bereits 16 Ziffern genügen für eine eindeutige Lösung, weiß niemand.

Als Annäherung an diese Frage haben Herzberg und Murty in ihrem Artikel Sudokus mit vier mal vier Kästchen untersucht. In solche Mini-Sudokus werden nur die Ziffern eins bis vier eingetragen, die Regeln gelten entsprechend.

In diesem Kleinformat genügen drei angegebene Ziffern nicht, um das Rätsel eindeutig lösbar zu machen, bewiesen die beiden Mathematiker, vier Ziffern aber schon.

Wie viele der Ziffern von eins bis neun in einem Sudoku in Originalgröße eingetragen sein müssen, haben Herzberg und Murty ebenfalls geklärt. Stehen nur sieben verschiedene Ziffern darin (manche davon dann natürlich mehrfach), kann die Lösung nicht eindeutig sein.

Sind etwa zu Beginn nur die Ziffern eins bis sieben eingetragen und hat man eine Lösung gefunden, so ergibt sich eine zweite, indem jede Acht durch eine Neun und jede Neun durch eine Acht ersetzt wird. Die beiden kanadischen Mathematiker geben jedoch ein Sudoku an, bei dessen 17 vorgegebenen Ziffern keine Neun auftaucht.

Bereits vergangenes Jahr haben der Deutsche Bertram Felgenhauer und der Engländer Frazer Jarvis gezählt, wie viele ausgefüllte Sudokus es gibt. Es sind mehr als sechs Trilliarden.

Viele von ihnen unterscheiden sich indes nur durch Spiegelungen oder Vertauschungen - zum Beispiel von zwei Zahlen im ganzen Rätsel oder von Zeilen, die alle zu der selben Dreiergruppe von Blöcken gehören. Berechnet man ausschließlich Anordnungen, die nicht durch solch einfache Änderungen verbunden sind, bleiben 5,5 Milliarden Sudokus möglich.

Die Kanadier Herzberg und Murty stellen in ihrem Artikel fest, dass die Situation bei den Mini-Sudokus mit vier mal vier Kästchen sehr übersichtlich ist. In diesem Format lassen sich nur zwei wesentlich verschiedene Rätsel konstruieren.

Für Abmessungen wie 16 mal 16, 25 mal 25 oder 36 mal 36 Kästchen können die Autoren die Anzahl der verschiedenen ausgefüllten Rätsel nur schätzen. Die Zahlen wachsen ins Unermessliche.

Mit Farbskala zum Stundenplan

Die mathematische Theorie der Sudokus ist relativ neu. Herzberg und Murty wandeln die Rätsel daher in ein Problem aus der seit langem erforschten Graphentheorie um.

Die Grundlagen dieser mathematischen Teildisziplin legte der Schweizer Leonhard Euler, der vor 300 Jahren geboren wurde. Ein Graph besteht aus Punkten, den "Knoten", und Verbindungen zwischen ihnen, den "Kanten".

Mathematiker übersetzen ein Sudoku in eine graphentheoretische Aufgabe, indem sie jedem der 81 Kästchen einen Knoten zuordnen. Zwei Knoten werden genau dann mit einer Kante verbunden, wenn sie zu Kästchen gehören, die in derselben Zeile, derselben Spalte oder demselben Block stehen.

Statt Ziffern verwenden Graphentheoretiker Farben. Ziel ist es, die Knoten mit neun verschiedenen Farben zu kolorieren, so niemals zwei Konten der gleichen Färbung verbunden sind. Eine Farbe steht also jeweils für eine Ziffer.

Solche Färbungsaufgaben treten nicht nur bei Sudokus auf, sondern zum Beispiel auch beim Verteilen von Rundfunkfrequenzen oder dem Anfertigen von Stundenplänen.

Für jede Stunde, die in einer Klasse unterrichtet werden soll, wird ein Knoten gezeichnet. Unterrichtsstunden, die gleichzeitig stattfinden, werden miteinander verbunden.

Schlüssel zur Lösung?

Nun bekommt jeder Lehrer eine Farbe und jeder Knoten wird mit der Farbe des Pädagogen belegt, der die Stunde halten soll. Sind dann niemals zwei gleichfarbige Knoten miteinander verbunden, ist gewährleistet, dass niemand zugleich in zwei Klassen stehen müsste.

Für Mathematiker lohnt es sich, Sudokus in Graphen umzuwandeln, da sie dann Ergebnisse und Methoden aus der etablierten Graphentheorie anwenden können.

Patentrezepte zur Lösung der Rätsel aber können und wollen die Forscher nicht liefern. Sie haben verstanden: Der Reiz von Sudokus besteht gerade in der Knobelei.

(1) www.ams.org/notices/200706/tx070600708p.pdf

(2) people.csse.uwa.edu.au/gordon/sudokumin.php

Bestens informiert mit SZ Plus – 4 Wochen kostenlos zur Probe lesen. Jetzt bestellen unter: www.sz.de/szplus-testen

URL:
www.sz.de/1.912970
Copyright:
Süddeutsche Zeitung Digitale Medien GmbH / Süddeutsche Zeitung GmbH
Quelle:
SZ vom 30.6./1.7.2007
Jegliche Veröffentlichung und nicht-private Nutzung exklusiv über Süddeutsche Zeitung Content. Bitte senden Sie Ihre Nutzungsanfrage an syndication@sueddeutsche.de.