Rätsel berechnet: Wann Sudokus eindeutig lösbar sind

Supercomputer-Rechenjahr zeigt, dass mindestens 17 vorgegebene Zahlen nötig sind, um ein solches Logikproblem ohne doppelte Varianten zu lösen
Typische Sudokus in Zeitungen und Magazinen geben deutlich mehr als 17 Hinweiszahlen vor.
© Sasse

Das „Kreuzworträtsel für Zahlenfans” – Sudoku – ist für Mathematiker weniger ein Zeitvertreib als eine harte Nuss. Denn statt sich aufs Ausfüllen der Kästchen zu beschränken, versuchen sie die Frage zu beantworten: Mit wie vielen Zahlen in den 9 mal 9 Feldern ist ein Sudoku eindeutig lösbar? Es sind 17, sagen jetzt irische Forscher. Sie konnten zwar keinen eleganten mathematischen Beweis vorlegen, lösten das Problem aber mit der Rechenkraft eines Supercomputers: Er konnte auch bei geschickter Vereinfachung in sieben Millionen Rechenstunden kein eindeutig lösbares 16-Zahlen-Sudoku finden. Dieses Ergebnis, online in der wissenschaftlichen Datenbank arXiv präsentiert, bestätigt, was Rätselfans seit Jahren vermuten. Auch Mathematiker halten die Lösung, die sie kürzlich auf einer Fachkonferenz in Boston erfuhren, für plausibel. Allerdings dürfte das Überprüfen wegen der enormen Rechenzeit eine Weile dauern. Derweil ist die Herangehensweise der Forscher auch für andere Bereiche interessant: Sie dürfte auch in der Gen-Analyse und Bioinformatik die Testauswertungen beschleunigen, ebenso wie bei Computernetzwerken und der Software-Entwicklung. ...



 

Home | Über uns | Kontakt | AGB | Impressum
© Wissenschaft aktuell & Scientec Internet Applications + Media GmbH, Hamburg