Numerator Die hohe Schule des Sudoku

Gehirnjogging mit Zahlenrätseln ist extrem beliebt. Was die wenigsten Rätselfreunde wissen: Hinter den Aufgaben steckt anspruchsvolle Mathematik. Wer das erfahren will, muss sich von Ziffern lösen - und in Farben und Linien denken.

Von


Bis vor wenigen Tagen hielt ich nicht besonders viel von Sudoku. Was sollte die Zahlenknobelei anderes sein als reichlich sinnfreier Zeitvertreib? Warum sollte man in einem neunmal neun Felder großen Quadrat nach fehlenden Zahlen suchen? Okay, für Ordnungsfanatiker mag das eine Herausforderung sein. Genauso wie ein nicht aufgeräumter Schreibtisch. Die Papiere müssen abgeheftet werden, die Zahlen eingetragen - so ist das halt, wenn ein geordnetes Umfeld gebraucht wird.

Möglicherweise hindert Sudoku auch manchen daran, auf dumme Gedanken zu kommen. Statt zu grübeln, zu zweifeln oder gar Revolutionen zu planen, lenkt man das Hirn mit Zahlenlogik ab.

Aber jetzt hat mich eine Veröffentlichung kanadischer Mathematiker eines Besseren belehrt. Agnes Herzberg und Ram Murty von der Queen’s University wandeln Sudoku-Rätsel in Farbspiele um. In den "Notices of the American Mathematical Society" fassen sie den Stand der Erforschung der Zahlenknobelei zusammen: Hinter Sudoku stecken komplizierte, teils ungelöste mathematische Probleme, die sich sehr gut mit der sogenannten Graphentheorie beschreiben lassen. Die vielen verrückten Zahlenkritzler in der U-Bahn leisten also womöglich einen bescheidenen Beitrag zum Fortschritt der Mathematik. Respekt!

Etwas Farbe, bitte!

Die Graphentheorie beschäftigt sich unter anderem mit dem Problem des Handlungsreisenden, also der Frage, in welcher Reihenfolge ein Außendienstler seine übers ganze Land verteilten Kunden besuchen muss, um den kürzestmöglichen Weg zurückzulegen.

Etwas Farbe reicht, um ein Sudoku-Puzzle graphentheoretisch zu beschreiben. Jedes der 81 Zahlenfelder stellt einen Knoten dar. Nun wird jeder Ziffer von 1 bis 9 eine Farbe zugeordnet, statt Ziffern finden sich so Farbkleckse in dem neun mal neun Felder großen Gitter. Die Sudoku-Regeln bestimmen dann, wie die 81 Knoten durch Linien miteinander verbunden werden. Jeder Knoten ist mit jedem anderen Knoten seiner Zeile und Spalte verbunden, und ebenso mit jedem Knoten seines drei mal drei Knoten großen Miniquadrats.

Wenn ein Sudoku-Puzzle richtig ausgefüllt ist, ist keiner der Knoten mit einem gleichfarbigen verbunden - denn das würde ja bedeuten, dass sich in einer Zeile, Spalte oder einem Miniquadrat zwei identische Ziffern befinden, was verboten ist. Mit dieser Knoten-Färbung und der Verbindungsregel ist Sudoku in die Graphentheorie überführt.

Eine Lösung, zwei oder gar keine?

Die Abstrahierung mag zunächst das Ganze noch komplizierter erscheinen lassen, als es tatsächlich ist. Die Graphentheorie macht die Rätselaufgaben jedoch mathematisch fassbarer. Für Herzberg und Murty ist Sudoku nichts anderes als eine Aufforderung zum Knotenfärben.

Ganz nebenbei erkennt man, dass Sudoku zum Beispiel ein ähnliches Problem ist wie die Vergabe von Radiofrequenzen an verschiedene Funktürme, deren Signale sich teilweise überlagern. Benachbarte Funktürme dürfen nicht identische Frequenzen nutzen, weil der Empfang sonst gegenseitig gestört wird. Die Frequenz steht somit für die Färbung des Knotens. Und wie bei Sudoku auch, stehen einzelne Färbungen/Frequenzen von vornherein fest, weil sie bereits früher vergeben wurden. Die Aufgabe lautet dann: Finde eine zulässige oder gültige Knotenfärbung für das gesamte System.

Ähnlich ist die Aufgabenstellung übrigens auch beim Aufstellen eines Stundenplanes einer Schule. Lehrer, Klassen und Räume müssen so aufgeteilt werden, dass Räumen oder Lehrern nicht zwei Unterrichtsstunden zugleich zugeordnet sind.

Dank der Graphentheorie können die kanadischen Mathematiker erste Aussagen dazu treffen, wie viele Lösungen eine Sudoku-Aufgabe hat. Doch sie stoßen auch an Grenzen: Es ist bekannt, dass es Sudoku-Puzzles mit 17 eingetragenen Ziffern gibt, die genau eine Lösung haben. Gordon Royle von der University of Western Australia hat Tausende davon gesammelt.

Aber gibt es vielleicht auch Puzzle mit nur 16 Einträgen? Niemand weiß es, auch Herzberg und Murty nicht. Und wer glaubt, dass ein Sudoku-Puzzle umso mehr mögliche Lösungen hat, je weniger Ziffern darin vorgegeben sind, liegt falsch. Es gibt beispielsweise ein Puzzle mit 29 eingetragenen Ziffern, das genau zwei Lösungen besitzt und nicht nur eine – siehe Kasten oben.

Zumindest eine Aussage darüber, wann es zwei Lösungen gibt, treffen Herzberg und Murty. Wenn nur sieben der neun Farben im Puzzle vorgegeben sind, dann sind zwei Lösungen möglich. Voraussetzung ist natürlich, dass überhaupt eine Lösung existiert. Der Beweis ist geradezu banal: Wenn zwei Farben noch nicht vorgegeben sind, dann können diese ja miteinander getauscht werden, und schon hat man zwei Lösungen.

Herzberg und Murty jedenfalls halten es für "bemerkenswert", dass in dem simplen Puzzle derartig schwierige mathematische Probleme stecken. "Es wäre zum Beispiel sehr spannend zu wissen, unter welchen Bedingungen ein teilkoloriertes System genau eine Lösung besitzt", schreiben sie.

Leider werden all die begeisterten Sudoku-Fans kaum zur Beantwortung dieser Frage beitragen können: Auch wenn sie alle jeden Tag Dutzende Puzzle lösen, werden die Rätselfans in überschaubarer Zeit kaum alle denkbaren Aufgaben abgearbeitet haben: Es gibt mehr als fünf Milliarden verschiedene Sudoku-Quadrate. Da lohnt sich das Abstrahieren dann doch.



insgesamt 119 Beiträge
Alle Kommentare öffnen
Seite 1
Sophie Amrain, 13.06.2007
1.
Zitat von sysopZahlenspiele für alle: Das Sodoku-Rätsel hat längst auch Europa erobert. Sodoku wurde zum Volkssport. Knobeln Sie auch über den Zahlen-Quadraten? Was mögen Sie daran? Oder ziehen Sie klassische Rätselarten vor?
Ist ganz lustig. Aber nach einem Weilchen sieht man wieder die Muster, dann wird es langweiliger. Das ist genauso wie bei den klassischen Rätseln.
DJ Doena 13.06.2007
2.
Ab und zu mach ich das schon, aber nur, wenn ich "nichts besseres" zu tun habe. Ich setze mich also nicht in meiner Freizeit an einen Tisch, um Zahlenmuster zu finden. Dafür hantiere ich in meinem Beruf mit Pointerarithmetik, das ist spannender.
SchneiderG 13.06.2007
3.
Zitat von sysopZahlenspiele für alle: Das Sodoku-Rätsel hat längst auch Europa erobert. Sodoku wurde zum Volkssport. Knobeln Sie auch über den Zahlen-Quadraten? Was mögen Sie daran? Oder ziehen Sie klassische Rätselarten vor?
Bin Gelegenheitsspieler. Wenn ich im Flugzeug 10 Stunden sitze lenkt das für einige Zeit etwas ab. Interessant war ein Sudoko mit den Zahlen 1-9 und den Buchstaben A-C (4x3 Felder). Da hat das tüfteln richtig Spaß gemacht.
klausab, 13.06.2007
4. gelegentlich
Ich löse auch nur gelegentlich Sudokus, idR solch, die als "mittel" oder "schwer" gekennzeichnet sind. Ab welcher Schwierigkeitsstufe wird es eigentlich nötig, in Alternativen zu arbeiten? Jedenfalls sehe ich hin und wieder in den Zügen Leute sitzen, die mit einem dünnen Bleistift kleine Zahlen in die Kästchen schreiben, was ich bisher noch nicht gebraucht habe, da es immer eine eindeutige Zahl gab.
UlliK 13.06.2007
5. Mit Verlaub -
aber Sodoku ist doch höchst lanfweilig! Das läuft immer nach demselben Schema ab: Wenn A, dann B; wenn C, dann nicht D usw. Da lobe ich mir die Kreuzworträtsel z.B. aus der ZEIT (um die Ecke gedacht), der Süddeutschen Zeitung (das Kreuz mit den Worten) oder der Neuen Zürcher Zeitung. Hier sind Phantasie, 'wilde' Assoziationen und nicht zuletzt auch Wissen gefragt. Was bei mir auch immer wieder zu einem Schmunzeln führt, wie z.B. heute morgen in der S-Bahn die Antwort auf die Frage So wenig durch- wie vorbeigängig: auf Wassergrünzeug versessene Vögel: Tangenten. (aus der ZEIT)
Alle Kommentare öffnen
Seite 1
Diskussion geschlossen - lesen Sie die Beiträge! zum Forum...

© SPIEGEL ONLINE 2007
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.