Wie ein gutes Sudoku entsteht: 17 Hinweise, eine Lösung und echte Schwierigkeit

Die meisten Menschen begegnen Sudoku als fertigem Produkt: ein Gitter mit einigen vorgegebenen Ziffern und einer Schwierigkeitsangabe darüber. Kaum jemand fragt, woher dieses Gitter eigentlich stammt. Wer hat entschieden, welche Felder sichtbar bleiben? Warum hat jedes ordentliche Rätsel genau eine Lösung? Und warum hält Sie ein als „leicht“ markiertes Rätsel zwanzig Minuten lang auf, während ein fast leeres Gitter schnell zerfällt? Hinter diesen Fragen steckt erstaunlich tiefe Mathematik, bis hin zu einem berühmten Computerbeweis, der ein Jahr Rechenzeit auf einem Supercomputer brauchte. Dieser Artikel erklärt das Ganze in einfacher Sprache und leitet daraus praktische Tipps für die Auswahl und das Lösen von Rätseln ab.

Wie viele Sudoku-Gitter gibt es?

Beginnen wir mit vollständig ausgefüllten Gittern: 9×9-Tabellen, in denen jede Zeile, jede Spalte und jeder 3×3-Block die Ziffern 1 bis 9 genau einmal enthält. Bertram Felgenhauer und Frazer Jarvis haben sie per Computer gezählt und das Ergebnis 2006 in der Zeitschrift Mathematical Spectrum veröffentlicht. Es gibt genau 6.670.903.752.021.072.936.960 davon, also rund 6,67 × 10²¹.

Viele dieser Gitter sind allerdings nur verkleidete Versionen desselben Gitters. Man kann die Ziffern umbenennen (jede 1 wird zur 7 und so weiter), Zeilen innerhalb eines Dreierbandes vertauschen, ganze Bänder tauschen, dasselbe mit Spalten tun oder das Gitter an der Diagonale spiegeln. Ed Russell und Frazer Jarvis zählten mit Hilfe des Lemmas von Burnside aus der Gruppentheorie, wie viele Gitter nach all diesen Umformungen wirklich verschieden bleiben. Laut McGuire und Kollegen dauerte die eigentliche Rechnung nur etwa eine Sekunde. Das Ergebnis: 5.472.730.538 „wesentlich verschiedene“ Gitter.

Anzahl vollständiger Sudoku-Gitter

Was gezählt wird	Anzahl	Quelle
Vollständige 4×4-Gitter (2×2-Blöcke)	288	McGuire, Tugemann & Civario
Vollständige 9×9-Gitter	6.670.903.752.021.072.936.960	Felgenhauer & Jarvis (2006)
Wesentlich verschiedene 9×9-Gitter	5.472.730.538	Russell & Jarvis (2007)

Das Minimum von 17 Hinweisen: Warum 16 unmöglich ist

Ein Rätsel ist ein Lösungsgitter, aus dem die meisten Ziffern gelöscht wurden. Löscht man zu viele, legen die verbleibenden Hinweise keine eindeutige Lösung mehr fest. Mit wie wenigen Hinweisen kommt ein ordentliches Rätsel also aus? Fans fanden zehntausende Rätsel mit 17 Hinweisen. Gordon Royle sammelte sie, und seine Liste wuchs schließlich auf 49.151 verschiedene 17er-Rätsel. Ein gültiges Rätsel mit 16 Hinweisen fand nie jemand. Doch „niemand hat eines gefunden“ ist kein Beweis.

Den Beweis lieferten Gary McGuire, Bastian Tugemann und Gilles Civario. Ihr Preprint erschien im Januar 2012, die begutachtete Fassung 2014 in der Fachzeitschrift Experimental Mathematics. Ihr Ansatz ist leicht zu beschreiben und war enorm schwer umzusetzen: jedes mögliche Lösungsgitter einzeln nach einem versteckten 16er-Rätsel zu durchsuchen.

Der Schlüssel ist die unvermeidbare Menge (unavoidable set). Stellen Sie sich vier Felder vor, verteilt auf zwei Zeilen, zwei Spalten und zwei Blöcke, mit dem Muster 3-8 / 8-3. Vertauscht man in diesen vier Feldern die 3en und 8en, entsteht ein anderes, völlig gültiges Gitter. Ist keines dieser vier Felder als Hinweis vorgegeben, hat das Rätsel also zwei Lösungen. Jedes vollständige Gitter enthält viele solcher Mengen, kleine wie große, und ein ordentliches Rätsel muss in jeder davon mindestens einen Hinweis haben. Mathematisch ist das ein Hitting-Set-Problem. Das Team schrieb dafür ein sehr schnelles Programm namens checker, das alle Hitting Sets aus 16 Feldern eines Gitters auflistet und prüft, ob eines davon eine eindeutige Lösung ergibt.

Dann ließen sie es über alle 5.472.730.538 wesentlich verschiedenen Gitter laufen. Die Suche lief von Januar bis Dezember 2011 auf dem Stokes-Cluster des Irish Centre for High-End Computing (ICHEC). Sie verbrauchte rund 7,1 Millionen Kernstunden, im Schnitt etwa 3,6 Sekunden pro Gitter. Die Autoren schreiben, dass die erste Version ihres Programms von 2006 dafür schätzungsweise 300.000 Prozessorjahre gebraucht hätte. Bessere Algorithmen drückten das auf etwa 800. Kein einziges 16er-Rätsel tauchte auf: 17 ist das echte Minimum.

Es gibt auch eine einfachere Tatsache mit einem Ein-Satz-Beweis: Ein ordentliches Rätsel muss mindestens acht der neun Ziffern als Hinweise zeigen. Fehlten etwa 4 und 6 beide, könnte man in der Lösung alle 4en und 6en vertauschen und hätte eine zweite gültige Lösung.

Warum eine einzige Lösung zählt (und Sie nie raten müssen)

Peter Norvig schreibt in seinem bekannten Essay über das Lösen von Sudokus: „Puzzles that appear in books and newspapers always have one unique solution.“ (Rätsel in Büchern und Zeitungen haben immer genau eine Lösung.) Das ist mehr als eine Konvention. Die Eindeutigkeit macht Sudoku zu einem Logikrätsel statt zu einem Glücksspiel.

Hat ein Rätsel genau eine Lösung, ist jedes Feld durch die Hinweise erzwungen. Es existiert also immer eine Kette von Schlussfolgerungen vom Start bis zum Ende, auch wenn sie lang und schwer zu finden ist. Bei zwei Lösungen kämen Sie irgendwann an einen Punkt, an dem in ein Feld sowohl die 2 als auch die 5 passt und nichts im Gitter verrät, welche richtig ist. Sie müssten raten, und in der Hälfte der Fälle würde die „richtige“ Lösung hinten im Heft Ihrem völlig logischen Ergebnis widersprechen.

Norvigs Essay zeigt auch, warum die Eindeutigkeit gezielt geprüft werden muss. Sein einfacher Zufallsgenerator füllt Felder, bis mindestens 17 Felder mit mindestens 8 verschiedenen Ziffern belegt sind. Das ist schnell, aber er weist darauf hin, dass das Ergebnis nicht garantiert eindeutig lösbar ist: Manche seiner Zufallsrätsel haben mehrere Lösungen, ein kleiner Teil gar keine.

Symmetrie und handgemachte Rätsel

Das Rätsel, das wir heute Sudoku nennen, erschien zuerst in den USA. Es wird meist Howard Garns zugeschrieben und 1979 von Dell Magazines unter dem Namen Number Place veröffentlicht. Der japanische Verlag Nikoli berichtet auf seiner Website, dass er das Rätsel in einem amerikanischen Magazin entdeckte, es 1984 den japanischen Lesern vorstellte und den langen japanischen Titel später zu „Sudoku“ verkürzte. Laut Nikoli setzte sich das Rätsel zunächst nur langsam durch. 1986 führten die Redakteure die Regel ein, dass die Hinweise in einem symmetrischen Muster stehen müssen, und danach wurde es ein großer Erfolg.

Am häufigsten ist die 180-Grad-Drehsymmetrie: Dreht man das Gitter auf den Kopf, landen Hinweisfelder wieder auf Hinweisfeldern. Auf die Logik hat das keinen Einfluss, es ist reine Ästhetik. Einen kleinen Preis hat es dennoch: Für Rätsel mit dieser Symmetrie liegt die geringste Hinweiszahl vermutlich bei 18, nicht bei 17.

Nikoli erstellt seine Rätsel bis heute von Hand. Auf der Seite, die das begründet, sagt Chefredakteur Nobuhiko Kanamoto: „Good Sudoku authors are always considering a solver’s feelings.“ (Gute Sudoku-Autoren denken immer an die Gefühle der Lösenden.) Ein menschlicher Autor kann einen befriedigenden Lösungsweg planen: einen sanften Einstieg, einen cleveren Schritt in der Mitte und ein sauberes Ende. Ein Computer kann endlos viele gültige Rätsel erzeugen. Ob sie dieses Gefühl von Gestaltung vermitteln, hängt davon ab, wie sorgfältig sie gefiltert werden.

Wie Computer-Generatoren meist arbeiten

Die meisten Sudoku-Websites, Apps und Rätselhefte nutzen Generatoren. Die Details unterscheiden sich, das übliche Vorgehen sieht aber so aus:

1. Ein volles Gitter erzeugen. Ein Backtracking-Löser mit Zufallsentscheidungen füllt ein leeres Gitter und erzeugt so eine zufällige gültige Lösung.
2. Hinweise entfernen. Felder werden einzeln geleert (oder in symmetrischen Paaren, wenn Symmetrie gewünscht ist).
3. Nach jedem Entfernen die Eindeutigkeit prüfen. Ein Löser zählt die Lösungen und bricht ab, sobald er eine zweite findet. Gibt es mehr als eine, kommt der letzte Hinweis zurück.
4. Das Ergebnis bewerten. Ein zweiter Löser, der menschliche Techniken nachahmt, arbeitet das Rätsel von leichten zu schweren Schritten durch und notiert die schwierigste nötige Technik.

Die Rätsel auf Ozerlyn Games folgen diesen Grundsätzen: Jedes Rätsel hat eine eindeutige Lösung und ist einer Schwierigkeitsstufe zugeordnet, sodass es allein mit Logik lösbar ist.

Schwierigkeit kommt von der Technik, nicht von der Hinweiszahl

Man nimmt leicht an, dass weniger Hinweise ein schwereres Rätsel bedeuten. Als grobe Faustregel stimmt das ein wenig, verlässlich ist es aber nicht. In einer Studie von 2012 in Scientific Reports maßen María Ercsey-Ravasz und Zoltán Toroczkai die Schwierigkeit von Rätseln mit einem mathematischen Modell. Ihre getesteten Rätsel mit 17 und 18 Hinweisen waren leichter als die schwersten Rätsel mit 21 oder 22 Hinweisen. Ihr Fazit: Die Schwierigkeit hängt auch davon ab, wo die Hinweise stehen, nicht nur davon, wie viele es sind.

Ein Vergleich in Worten: Rätsel A hat nur 24 Hinweise, aber sie sind so verteilt, dass in jeder Phase eine Ziffer in einer Zeile, Spalte oder einem Block nur noch einen möglichen Platz hat. Man findet einfach versteckte Einer (Hidden Singles), bis das Gitter voll ist. Rätsel B hat 30 Hinweise, doch nach einem Dutzend einfacher Einträge hat jedes verbleibende Feld zwei oder drei Kandidaten und kein Einer ist mehr übrig. Um weiterzukommen, braucht man einen X-Wing oder eine Kette. Trotz der Hinweiszahlen ist A leicht und B schwer.

Deshalb messen ernsthafte Bewertungssysteme die benötigten Techniken. Am bekanntesten ist das Sudoku-Explainer-Rating (SE), das ein Rätsel nach dem schwierigsten nötigen Schritt bewertet: Einer erhalten niedrige Werte, Paare und X-Wings höhere, Ketten und Forcing Nets noch höhere. Unser Artikel Sudoku SE-Rating erklärt beschreibt die Skala im Detail, und mit dem SE-Rating-Rechner können Sie jedes Rätsel selbst bewerten.

Was das für Sie als Spieler bedeutet

• Wählen Sie Rätsel nach Bewertung, nicht danach, wie leer sie aussehen. Ein spärliches Gitter ist nicht automatisch schwer, ein volles nicht automatisch leicht.
• Wenn sich ein „leichtes“ Rätsel schwer anfühlt, suchen Sie wahrscheinlich nur nach nackten Einern (Feldern mit nur einem Kandidaten). Leichte Rätsel beruhen oft auf versteckten Einern. Fragen Sie „Wo kann die 7 in diesem Block hin?“ statt „Was passt in dieses Feld?“
• Wenn Sie glauben, raten zu müssen, haben Sie etwas übersehen. Bei einer eindeutigen Lösung gibt es immer einen logischen nächsten Schritt. Prüfen Sie Ihre Notizen, bevor Sie etwas Riskantes versuchen.
• Eindeutigkeit ist ein Werkzeug. Fortgeschrittene nutzen die Tatsache, dass es nur eine Lösung gibt, um Muster wie das 3-8 / 8-3-Rechteck von oben auszuschließen. Darauf beruht die Technik „Unique Rectangle“.

Zum Üben spielen Sie ein Rätsel auf Ihrem Niveau auf unserer Online-Sudoku-Seite oder drucken Sie einige über Sudoku zum Ausdrucken aus und lösen Sie sie mit dem Bleistift. Achten Sie dabei jeweils auf den schwierigsten Schritt.

Quellen

1. Gary McGuire, Bastian Tugemann, Gilles Civario: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics 23(2), 2014, S. 190–217.
2. Derselbe Artikel als frei zugänglicher Preprint: arXiv:1201.0749 (mit den Gitterzahlen, Royles Liste mit 49.151 Rätseln und den Rechendetails).
3. Bertram Felgenhauer, Frazer Jarvis: Mathematics of Sudoku I, Mathematical Spectrum 39(1), 2006. Zusammenfassung der Methode: Cornell University, „Counting Sudoku solutions“.
4. Ed Russell, Frazer Jarvis: Mathematics of Sudoku II, Mathematical Spectrum 39(2), 2007. Überblick: Mathematics of Sudoku (Wikipedia).
5. María Ercsey-Ravasz, Zoltán Toroczkai: The Chaos Within Sudoku, Scientific Reports 2, 725, 2012.
6. Peter Norvig: Solving Every Sudoku Puzzle.
7. Nikoli: Sudoku (Geschichte des Rätsels) und Why hand made?
8. Sudoku (Wikipedia): Geschichte, Howard Garns und Dells Number Place.