Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten von Spektrum der Wissenschaft 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 Sudoku

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…

April 2012

Dieser Artikel ist enthalten in Spektrum der Wissenschaft April 2012

Kennen Sie schon …

Juli 2016

Spektrum der Wissenschaft – Juli 2016

In dieser Ausgabe widmet sich "Spektrum der Wissenschaft" Leibniz. Außerdem im Heft: Wie lange lebt ein Neutron, Verblüffende Lebensfülle unter dem Schelfeis

Highlights 2/2015

Spektrum der Wissenschaft – Highlights 2/2015: 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?

Spezial Physik - Mathematik - Technik 3/2013

Spektrum der Wissenschaft – Spezial Physik - Mathematik - Technik 3/2013: Die neue Computer-Ära

Wolkige Aussichten: Chancen und Gefahren des Cloud Computing • Vertraulichkeit im Netz: Wie sich Big Brother in die Schranken weisen lässt • Die kleinsten Bits der Welt: Elektrische Widerstände als Schaltelemente und Speicher

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. 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