Standort: science.ORF.at / Meldung: "Antwort auf das Sudoku-Rätsel: 17"

Jemand füllt ein Sudoku aus

Antwort auf das Sudoku-Rätsel: 17

Die übliche Herausforderung von Sudokus besteht darin, fehlende Zahlen in ein quadratisches Raster einzufügen. Es gibt aber auch ein mathematisches Sudoku-Rätsel, nämlich die Frage, wie viele Ziffern vorgegeben sein müssen, damit es nur eine eindeutige Lösung gibt. Ein irischer Mathematiker sagt nun: 17.

Mathematik 09.01.2012

Mit 16 oder weniger Ziffern zu Beginn gibt es keine eindeutige Lösung, schreiben Gary McGuire vom University College in Dublin und Kollegen in einer online veröffentlichten Studie.

Die Studie:

"There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem" von Gary McGuire und Kollegen ist auf dem Preprint-Server "arXiv.org" erschienen.

Trilliarden von Varianten

Sudokus, in den USA erfunden, aber dann in Japan populär geworden, zählen heute auch in Österreich zu den beliebtesten Formaten von Rätselfreunden. Ziel ist es, ein Gitter aus 9x9 Flächen derart mit den Ziffern von eins bis neun zu füllen, dass jede in jeder Zeile, jeder Spalte und jedem Block nur genau einmal verwendet wird.

Zu Beginn sind einige der Ziffern bereits vorgegeben: je weniger desto schwieriger ist die Aufgabe. Einfache Sudokus haben 25 oder mehr Ziffern, schwierige 20 oder weniger. In den Zeitungen liegt der Durchschnittswert bei 25. Dass es mit 17 eine Grenze gibt, unterhalb der es keine eindeutige Lösung gibt, ist von Rätselfreunden empirisch schon oft beobachtet worden.

Mathematisch bewiesen wurde das bisher aber noch nicht. Und das liegt in erster Linie daran, dass die Möglichkeiten dazu riesig groß sind: Laut unterschiedlichen Berechnungen gibt es rund 6,7 Trilliarden Suduko-Varianten.

Sieben Millionen Stunden Rechenzeit

Für den mathematischen Beweis, dass 17 tatsächlich die Untergrenze für eindeutige Lösungen darstellt, hat es deshalb einer ganzen Menge Rechenzeit bedurft: Sieben Millionen Stunden sind es geworden, bis der von Gary McGuire am Computerzentrum in Dublin entworfene Algorithmus endlich das gewünschte Resultat liefern konnte.

Eine Konsequenz davon ist, dass es eine ganze Zeit dauern könnte, um die Berechnungen zu überprüfen. Die US-Mathematiker-Gemeinde, die sich vergangene Woche in Boston traf, hält die Arbeit jedenfalls für wertvoll, wie "Nature" berichtet. Mc Guire selbst füllt laut dem Magazin hin und wieder Sudokus aus, bevorzugt "aber ehrlich gesagt Kreuzworträtsel".

Lukas Wieselberg, science.ORF.at

Mehr zu dem Thema:

Mehr aus science.ORF.at

E-Mail an die Redaktion

Die ORF.at-Foren sind allgemein zugängliche, offene und demokratische Diskursplattformen. Die Redaktion übernimmt keinerlei Verantwortung für den Inhalt der Beiträge. Wir behalten uns aber vor, Werbung, krass unsachliche, rechtswidrige oder beleidigende Beiträge zu löschen und nötigenfalls User aus der Debatte auszuschließen. Es gelten die Registrierungsbedingungen.

Forum

 

  • Die härteste Variante

    algu, vor 44 Tagen, 20 Stunden, 24 Minuten

    beim Sudoku ist der Einsatz von einem Kugelschreiber :-))

  • logopezi, vor 45 Tagen, 1 Stunde, 58 Minuten

    ok, mit mindestens 17 zahlen kann man also ein eindeutiges sudoko bauen.
    udn jetzt umgekehrt: wie viele darf es maximal enthalten, um trotzdem noch mehr als eine lösung zu ermöglichen? ich glaube, 79 von 91, oder?

    • logopezi, vor 45 Tagen, 1 Stunde, 58 Minuten

      von 81 natürlich.

    • ranzoni, vor 44 Tagen, 20 Stunden, 37 Minuten

      Ich tippe auf 77, denn um 2 Ziffern zu vertauschen (dann hat man 2 Lösungen) braucht man 4 Felder.

    • 77 von 81 Zahlen gegeben - trotzdem nicht eindeutig

      oldprogrammer, vor 44 Tagen, 15 Stunden, 33 Minuten

      Ich bin auch für die 77 von 81. Hier ein derartiges Sudoku mit einem freien Karo für die Zahlen 1 und 5, das 2 gültige Lösungen zulässt:
      ++---+---+---++---+---+---++---+---+---++
      ++---+---+---++---+---+---++---+---+---++
      || 9 | 1 | 8 || 7 | 3 | 2 || 5 | 4 | 6 ||
      ++---+---+---++---+---+---++---+---+---++
      || 2 | 5 | 7 || 4 | 6 | 8 || 9 | 3 | 1 ||
      ++---+---+---++---+---+---++---+---+---++
      || 4 | 3 | 6 || 9 | 1 | 5 || 7 | 8 | 2 ||
      ++---+---+---++---+---+---++---+---+---++
      ++---+---+---++---+---+---++---+---+---++
      || 8 | 2 | . || . | 7 | 3 || 4 | 6 | 9 ||
      ++---+---+---++---+---+---++---+---+---++
      || 6 | 4 | . || . | 8 | 9 || 3 | 2 | 7 ||
      ++---+---+---++---+---+---++---+---+---++
      || 7 | 9 | 3 || 6 | 2 | 4 || 1 | 5 | 8 ||
      ++---+---+---++---+---+---++---+---+---++
      ++---+---+---++---+---+---++---+---+---++
      || 3 | 7 | 2 || 8 | 4 | 1 || 6 | 9 | 5 ||
      ++---+---+---++---+---+---++---+---+---++
      || 1 | 8 | 9 || 3 | 5 | 6 || 2 | 7 | 4 ||
      ++---+---+---++---+---+---++---+---+---++
      || 5 | 6 | 4 || 2 | 9 | 7 || 8 | 1 | 3 ||
      ++---+---+---++---+---+---++---+---+---++
      ++---+---+---++---+---+---++---+---+---++

      Mehr Felder...