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

Kennen Sie schon …

Spektrum der Wissenschaft – Unendlichkeiten

Die Mathematik des Grenzenlosen - Mengenlehre: Wie ordnet man das Unermessliche? • Arithmetische Dynamik: Zahlenfolgen in Bewegung • Kategorientheorie: Überblick durch Abstraktion

Spektrum - Die Woche – Auf der Suche nach dem inneren Kind

Seit dem 1. Juli steht fest, dass die Benin-Bronzen zurück an Nigeria gehen. Doch wie kam die britische Kriegsbeute eigentlich überhaupt nach Deutschland? Diskussionen lösen auch andere Mitbringsel aus, und zwar jene vom Mars. Die gute Nachricht: Zurückfordern wird die Steine wohl niemand.

Spektrum - Die Woche – Mama, Papa, ich will Euch nie wiedersehen!

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.

Schreiben Sie uns!

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, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften 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 Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften 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