Unvorstellbar viele Sudokus

Radio
// 18 Februar 2016
Halbausgefülltes Sudoku (Bild: FreeImages.com/Martin Boose)

Bei einem Sudoku-Rätsel muss ein 9×9-Gitter mit den Ziffern 1 bis 9 so ausgefüllt werden, dass jede Ziffer in jeder Spalte, in jeder Zeile und in jedem 3×3-Unterblock genau ein Mal vorkommt. Wie viele mögliche Kombinationen gibt es?

Einige Ziffern sind bei einem Sudoku-Rätsel schon vorgegeben. Solche Rätsel werden erzeugt, indem zuerst das komplett ausgefüllte Sudoku-Gitter konstruiert wird; danach werden einzelne Felder gelöscht.

Sudoku-Gitter werden per Computer gefüllt

Das Ausfüllen des 9×9-Sudoku-Gitters geschieht durch Ausprobieren, allerdings macht das ein Computer: Die Felder werden nach und nach mit Ziffern gefüllt, und sobald durch das Einsetzen einer Ziffer eine der Regeln verletzt ist, wird eine andere Ziffer gewählt. Ein Computer schafft das in Sekundenschnelle. Es gibt etwa 6,7 Trilliarden verschiedene Möglichkeiten, ein Sudoku-Gitter regelkonform mit Ziffern zu füllen.

6,7 Trilliarden verschiedene Möglichkeiten

Aus streng mathematischer Sicht ist die Zahl allerdings kleiner, denn Mathematiker zählen zwei verschiedene Sudokus nur als eines, wenn das eine aus dem anderen durch eine einfache Operation wie durch das Vertauschen zweier Zeilen hervorgeht. Fasst man all die strukturell ähnlichen Sudokus zusammen, dann gibt es nur 5,5 Milliarden (wesentlich) verschiedene ausgefüllte Sudoku-Gitter.

Rätsel werden durch Weglassen von Ziffern erzeugt

Auch das Erzeugen des Rätsels, das heißt das Weglassen einzelner Ziffern aus dem komplett ausgefüllten Gitter, macht man mit einem Computer. Hierbei muss man beachten, dass das Rätsel am Ende eindeutig bleibt, es also nicht zwei verschiedene Möglichkeiten gibt, die leeren Felder auszufüllen. Das wird nach jedem Weglassen einer Ziffer schnell überprüft. Sollte dabei ein Rätsel mit mehreren Lösungen entstanden sein, wird der Schritt rückgängig gemacht und ein anderes Feld gelöscht.

Unvorstellbar viele Rätsel-Möglichkeiten

Es gibt sehr viele Möglichkeiten, aus jedem der 6,7 Trilliarden ausgefüllter Sudoku-Gitter durch Weglassen Sudoku-Rätsel zu erzeugen. Die Zahl könne man nicht ausrechnen, sagt der Mathematiker Prof. Ulrich Görtz von der Universität Duisburg-Essen, es aber man könne schätzen, dass sie 38 Stellen hat.

18.02.2016
WDR 5, Leonardo, Die Kleine Anfrage

Kategorien
Radio