Mathematik: Berechnungen

Sudoku: Gibt es immer nur eine Lösung?

Hat mein Sudoku überhaupt eine Lösung? Hat es vielleicht mehrere oder ist meine Lösung die einzige? Solche Fragen beantworten Forscher der kanadischen Queen's University mit der Mathematik. Sie ordneten jedem der neun Ziffern eine Farbe zu und machten so die möglichen Anordnungen auf den 81 Feldern für die Analyse sichtbar.

Ihr Ergebnis: Acht der neun Zahlen müssen vorgegeben sein, damit ein Sudoku eine einzige, eindeutige Lösung hat. Bei nur 7 der Zahlen sind mindestens zwei Lösungen möglich. Ebenso müssen für eine einzige Lösung mindestens 17 Felder ausgefüllt sein. Andererseits heißt das nicht, dass mehr als 17 Felder immer eine einzige Lösung liefern: Die Mathematiker geben ein Beispiel mit 29 ausgefüllten Feldern, das zwei Lösungen hat.

Solche Analysen haben einen ernsthaften Hintergrund: Sie werfen neue, ungelöste Probleme der Graphentheorie auf. "Zum Beispiel, ob es ein Sudoku-Puzzle gibt, das mit 16 oder weniger Einträgen eine einzige Lösung hat", schreiben Agnes M. Herzberg und M. Ram Murty im Fachblatt "Notices of the American Mathematical Society".

Sudokus gehen übrigens so schnell nicht aus: Die Zahl aller unterschiedlichen liegt bei 5,5 Milliarden.

( wsa )

Mehr Artikel aus dieser Rubrik gibt's hier: Forschung