Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Kombinatorik: Ein Sudoku benötigt mindestens 17 Vorgaben

Um diese Vermutung zu beweisen, haben Gary McGuire und seine Kollegen einen Supercomputer fast fünfeinhalb Milliarden Möglichkeiten durchprobieren lassen.
Neu SudokuLaden...

Das Knobelspiel Sudoku ("einsame Zahlen") eroberte vor etlichen Jahren von Japan aus die Welt und hat auch nach dem Abflauen der ersten Begeisterungswoge immer noch einen festen Platz in Tageszeitungen und auf Internetseiten. Es geht darum, ein quadratisches Brett aus 9 mal 9 Feldern so mit den Zahlen von 1 bis 9 zu füllen, dass jede der Zahlen in jeder Zeile, jeder Spalte und in jedem Teilkästchen der Größe 3  · 3 genau einmal vorkommt (Spektrum der Wissenschaft 3/2006, S. 100). Die Belegung gewisser Felder ist vorgegeben.

Ein Sudoku-Rätsel ist nur dann richtig gestellt, wenn diese Vorgaben die Lösung eindeutig bestimmen. Es darf also zu ein und derselben Vorgabemenge keine zwei vollständig und regelgerecht ausgefüllte Sudoku-Bretter geben.

Weit entfernt von dem kreuzworträtselartigen Zeitvertreib aus der Tageszeitung wetteifern die harten Sudoku- Profis darum, aus möglichst wenigen Vorgaben die komplette Belegung zu erschließen. Im Prinzip ist ein Rätsel umso schwerer, je weniger Information es bereitstellt. Die härtesten unter ihnen fordern vom Löser, aus nur 17 Vorgaben zu erschließen, was in die restlichen 64 Felder gehört...

Kennen Sie schon …

07/2021

Spektrum - Die Woche – 07/2021

Warum brechen Kinder den Kontakt zu ihren Eltern ab? Und wie können diese damit umgehen? Darüber lesen Sie mehr in dieser Ausgabe. Außerdem: Hilberts 13. Problem und ein erfolgreicher falscher Entdecker.

Highlights 1/2021

Spektrum der Wissenschaft – Highlights 1/2021: Mathematische Spiele und Strategien

Ziegenproblem: Ist hinter der nächsten Tür eine Ziege oder das Auto? • Gefangenendilemma: Kooperieren, betrügen oder ganz aussteigen? • Strategien der besten Wahl: Wie lange soll die Prinzessin auf den Traumprinzen warten?

45/2019

Spektrum - Die Woche – 45/2019

In dieser Ausgabe widmen wir uns der Schilddrüse, Waldbränden und den Habsburgern.

Lesermeinung

2 Beiträge anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Erratum

Das auf Seite 18 angegebene "eindeutig lösbare Sudoku mit nur 17 Vorgaben" ist nicht eindeutig lösbar! Mehrere Leser haben mehrfache Lösungen dieses Rätsels angegeben. Gary McGuire, einer der Autoren der dem Artikel zu Grunde liegenden Arbeit, hat inzwischen bestätigt, dass ein Druckfehler vorliegt. Die Neufassung seiner Arbeit gibt es hier. In dem auf Seite 18 abgedruckten Sudoku sind die Zahlen 4 und 3 ein Feld nach rechts zu verschieben; sie sollen also nicht, wie abgedruckt in den Spalten 7 und 8, sondern in 8 und 9 stehen.

Christoph Pöppe, Redaktion