Sudoku:Die Suche nach der kniffligsten Kombination

Lesezeit: 3 min

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.

Sudoku: Welche Zahl in welches Kästchen - Sudoku hält geistig fit.

Welche Zahl in welches Kästchen - Sudoku hält geistig fit.

(Foto: Foto: iStockphoto)

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.

Zur SZ-Startseite
Süddeutsche Zeitung
  • Twitter-Seite der SZ
  • Facebook-Seite der SZ
  • Instagram-Seite der SZ
  • Mediadaten
  • Newsletter
  • Eilmeldungen
  • RSS
  • Apps
  • Jobs
  • Datenschutz
  • Abo kündigen
  • Kontakt und Impressum
  • AGB