Die Suche nach der kniffligsten Kombination

Welche Zahl in welches Kästchen - Sudoku hält geistig fit. (Foto: iStockphoto)

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.

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.

mehr zum Thema
Hier geht's zum Spiel Sudoku   Sudoku-Nachfolger Warten auf Kakuro   Sudoku Wer hat’s erfunden?   Mathematik Neun Ziffern gegen einen   Hirn-Fitness Geistige Altersvorsorge

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.

vorherige Seite     1 | 2     nächste Seite

ANZEIGE

Themen

Agnes Herzberg, Bertram Felgenhauer, Frazer Jarvis, Gordon Royle, Leonhard Euler, Mathematiker, Mensch, Methode, Milliarden, Millionen, Mini, Problem, Pädagoge, Ram Murty, Regel, Reiz, Rätsel, Sudoku, Universität, Wissenschaftler, Zeitschrift

Weitere Artikel in Wissen

Leserkommentare (0) Wir wollen die Qualität der Nutzerdiskussionen stärker moderieren. Bitte haben Sie deshalb Verständnis, dass wir die Kommentare ab 19 Uhr bis 8 Uhr des Folgetages einfrieren. In dieser Zeit können keine Kommentare geschrieben werden. Dieser "Freeze" gilt auch für Wochenenden (Freitag 19 Uhr bis Montag 8 Uhr) und für Feiertage.