Sudoku

Sūdoku (jap. 数独, wörtlich Zahlen-Einzel) ist ein Zahlenpuzzle. Das Puzzlefeld besteht aus einem Quadrat, das in 3 × 3 Unterquadrate bzw. Blöcke eingeteilt ist. Jedes Unterquadrat ist wieder in 3 × 3 Felder eingeteilt, sodass das Gesamtquadrat also 81 Felder (= 9·9 Felder) bzw. 9 Reihen und 9 Spalten mit je 9 Feldern besitzt.

Ein Sūdoku-Rätsel

In einige dieser Felder sind schon zu Beginn Ziffern (1 bis 9) eingetragen. Typischerweise sind 22 bis 36 Felder von 81 möglichen vorgegeben. Das Puzzle muss nun so vervollständigt werden, dass

• in jeder Zeile,
• in jeder Spalte und
• in jedem der neun Blöcke jede Ziffer von 1 bis 9 genau einmal auftritt.

Inzwischen gibt es auch Sūdokus mit 4 × 4 Unterquadraten und somit 256 (= 16·16) Feldern, in die 16 verschiedene Zahlen, Buchstaben oder Symbole verteilt werden. Ebenso sind 5 × 5 Sūdokus denkbar, etc. Für Kinder gibt es Sūdokus mit einer Kantenlänge von 2 pro Unterquadrat, also werden dort nur 4 Ziffern oder Bildsymbole benötigt. Eine weitere Variante sind Sudokus mit treppenförmiger Begrenzung der Blöcke (engl. Staircase Sudoku).

Ursprung

Ein ähnliches Rätselspiel wurde unter dem Namen „Carré latin“ (Lateinisches Quadrat) vom Schweizer Mathematiker Leonhard Euler im 18. Jahrhundert erfunden; im Gegensatz zu Sudoku ist dieses nicht in Blöcke (Unterquadrate) unterteilt. Seinen Durchbruch erlangte das Sūdoku jedoch erst, als die japanische Zeitschrift Nikoli solche Rätsel regelmäßig abdruckte. Zu diesem Zeitpunkt erhielt das Zahlenrätsel seinen heutigen Namen. Diese Rätselart ist seit 2005 über die britische Zeitung The Times auch in Europa populär geworden und gehört inzwischen zum Standard vieler Rätselseiten in Zeitungen.

Lösungsmethoden

Intuitiv

Lösungsansatz am abgebildeten Beispiel: Wenn man in das Unterquadrat rechts unten die 1 eintragen will, so legt die 1 in der Mitte der vorletzten Zeile fest, dass in dieser Zeile sonst keine 1 stehen darf. Ebenso scheidet die letzte Spalte aus, da dort weiter oben schon eine 1 steht. Die einzige verbleibende Möglichkeit ist also das freie Feld in der untersten Zeile dieses Unterquadrats.

Analytisch-systematisch

1. Durch Ausschluss:
   Man sucht die Spalte, Reihe oder das Quadrat (sog. "Neuner-Einheit") mit den wenigsten Leerstellen heraus und notiert die fehlenden Ziffern auf einem separaten Blatt, um den Überblick zu behalten. In dem Sūdoku der Abbildung z.B. die 5. Spalte. Hier fehlen 3, 4, 5. Nun schreibt man mit Bleistift in die freien Felder alle möglichen Ziffern. In der 3. Reihe also alle: 3, 4, 5. Da in der 5. Reihe nur die 5, und in der 7. Reihe nur die 3 stehen kann, kann man in der 3. Reihe die überzähligen Zahlen 3 und 5 streichen, wobei 4 stehen bleibt. Die Reihe ist komplett und man kann die korrekten Ziffern mit einer anderen Farbe oder mit Kugelschreiber fixieren. Dann wendet man sich der nächsten Neuner-Einheit zu usw. Auf einfache Weise lassen sich alle Kästchen füllen. Je nach Anzahl der vorgegebenen Ziffern muss man zunächst eine Zeit lang in einer größeren oder kleineren Anzahl von Kästchen zwei oder mehrere Ziffern stehen lassen, ehe klar wird, welche Ziffer die richtige ist.
2. Durch Kombination:
   Enthalten zwei Neuner-Einheiten in einer Reihe die gleiche Ziffer (z.B. im obigen Beispiel die Ziffer 5 in der Neuner-Einheit oben links und oben Mitte), so kann die Position der Ziffer in der dritten Neuner-Einheit der Reihe oft direkt ermittelt werden: In der dritten Neuner-Einheit muss die Ziffer in der noch nicht mit der Ziffer belegten Reihe sein. Wenn nun für die Ziffer in der dritten Neuner-Einheit nur noch eine Spalte übrigbleibt - weil die anderen Felder der Reihe in Neuner-Einheit 3 schon belegt sind oder die entsprechende Spalte in einer anderen Neuner-Einheit die Ziffer schon enthält - so kann die Ziffer sofort eingetragen werden. Das Gleiche gilt analog für Spalten. Im Beispiel oben wird so schnell klar, dass Ziffer 5 in der rechten oberen Neuner-Einheit in der linken unteren Zelle stehen muss
   (Illustration siehe en:sudoku, Scanning-Methode)

Algorithmisch

Eine Methode zum Lösen eines Sūdoku ist die Behandlung als Schnittmengenproblem. Aus den vorgegebenen Ziffern lässt sich für jedes Feld eine Menge von Kandidatenziffern bestimmen, die für ein Feld die Schnittmenge aus je drei Mengen ist: Diese sind die Komplemente der jeweils in der selben Zeile, Spalte und im selben Quadrat enthaltenen Ziffern zur Menge aller Ziffern (ohne die Null). In einfachen Fällen hat das Rätsel die Eigenschaft, dass mindestens ein Feld eine einelementige Kandidatenmenge besitzt, oder dass ein Element aus einer Kandidatenmenge eines Feldes nicht in den Kandidatenmengen aller anderen Felder der selben Spalte oder Zeile oder des selben Quadrats vorkommt. Dieser Kandidat kann dann fest in das jeweilige Feld eingesetzt werden und die betreffende Ziffer aus den Kandidatenmengen der übrigen Felder in der selben Zeile, Spalte und im selben Quadrat entfernt werden. Dieses Verfahren wird dann solange wiederholt, bis alle Zellen aufgefüllt sind.

• $M=\{1\cdots 9\}$ Ziffern
• $Z_{1}\cdots Z_{9}$ Mengen der in je einer Zeile enthaltenen Ziffern
• $S_{1}\cdots S_{9}$ Mengen der in je einer Spalte enthaltenen Ziffern
• $Q_{1,1}\cdots Q_{3,3}$ Mengen der je in einem Teilquadrat enthaltenen Ziffern

Die Kandidatenmenge $K_{i,j}$ eines Feldes $F_{i,j}$ berechnet sich dann in jedem Iterationsschritt wie folgt:

$K_{i,j}=(M\setminus Z_{i})\ \cap \ (M\setminus S_{j})\ \cap \ (M\setminus Q_{\lfloor {\frac {i}{3}}\rfloor ,\lfloor {\frac {j}{3}}\rfloor })$

Bei den meisten eindeutig lösbaren Rätseln, insbesondere den schwierigen, führt diese Methode allein nicht zur Lösung. In diesen Fällen müssen z.B. Paare oder Tripel von Kandidaten gemeinsam betrachtet werden, um die Kandidatenmengen in einem ersten Schritt zu verkleinern. Alternativ kann, falls in einem Iterationsschritt keine einelementige Kandidatenmenge existiert, aus einer der (kleinsten) Kandidatenmengen eine Zahl ausgewählt werden, um eine der mehreren möglichen Lösungen zu erhalten (Versuch und Irrtum-Methode).

Nach der Backtracking-Methode

Auf dem Computer kann man ein Sudoko mit der Backtracking-Methode lösen. Beginnend mit dem ersten freien Feld, probiert man systematisch, mit der Eins beginnend, ob man zu einer Lösung kommt. Beim ersten Widerspruch geht man zurück (engl. backtrack). Dieser Lösungsweg lässt sich sehr elegant rekursiv formulieren, und man ist sicher, dass alle Kombinationsmöglichkeiten abgesucht werden. Da es sich um tausende Wege handeln kann, ist dieser Algorithmus nur für Computerprogramme geeignet. Der Lösungsalgorithmus ist sicher nur suboptimal, da er keinerlei analytische Vorinformationen verwendet und nur durch Ausprobieren vorgeht. Es stellt also den schnellen Weg zu einer Lösung, aber nicht unbedingt einen schnellen Lösungsweg dar.

Erstellung neuer Sudokus

Schwieriger als das Lösen der Puzzle dürfte das Herstellen sein.

• Eindeutige Lösung: Es soll nur eine korrekte Lösung existieren.
• Gewünschter Schwierigkeitsgrad: Die Anzahl der vorgegebenen Ziffern bestimmt nicht allein den Schwierigkeitsgrad. Die Anordnung spielt eine entscheidende Rolle.

Algorithmus

1. Belegung des gelösten Puzzles erstellen
   • 1. Weg: Ein leeres Puzzlefeld wird Zelle für Zelle durch "Auswürfeln" (Zufallsgenerator) mit Ziffern befüllt. Sobald es zu einem Regelverstoß kommt, muss per Backtracking-Methode eine andere Belegung probiert werden. Dies ist weniger trivial, als beim Lösen des Puzzles: Da eine möglichst "zufällige" Belegung des Puzzlefeldes benötigt wird, kann man nicht einfach alle Ziffern der Reihe nach durchprobieren. Es hindert aber nicht, alle Ziffern, sobald sie einmal "ausgewürfelt" wurden als künftig - für die jeweilige Zelle - gesperrt "abzuhaken" (in einer Tabelle zu markieren)
   • 2. Weg: Neun Einsen ohne Regelverstoß im Puzzelfeld verteilen. Dann neun Zweier, neun Dreier, usw. verteilen. Auch hier muss ein Backtracking-Algorithmus angewandt werden.
   • 3. Weg: Man füllt eine Zeile oder eine Spalte in beliebiger Reihenfolge mit den erlaubten Ziffern, verschiebt dann mit jeder weiteren Zeile/Spalte die Ziffernfolge, bis man am Schluss alle möglichen Varianten untereinander/nebeneinander in einer n x n Matrix vorliegen hat. Dies alleine wäre ein äußerst trivial zu lösendes Rätsel, da sich die Ziffernfolgen wiederholen, deswegen sollte man über erlaubte Transformationen diese Matrix nun schrittweise so verändern, dass die Ursprungsziffernfolge sowie die ausgeführten Transformationen nicht mehr nachvollziehbar sind. Erlaubte Transformationen sind, z.B., das Invertieren, das Spiegeln (vertikal, horizontal, schräg), Rotieren, Vertauschen ganzer Zeilen oder Spalten, sofern sie innerhalb eines Mini-Quadrates bleiben, - oder das Vertauschen ganzer Zeilen und Spalten von Miniquadraten. Etliche dieser Transformationen hintereinander verwischen (fast) alle Hinweise auf die ursprüngliche Ziffernfolge. Von den hier vorgestellten Erstellungsmethoden ist diese die am wenigsten aufwendige und rechenintensive.
2. Zur Lösung passendes Sudoku-Rätsel erzeugen
   • Wiederum durch "Auswürfeln" werden je nach Schwierigkeitsgrad zwischen 45 und 57 Ziffern wieder entfernt. Ohne weitere Kontrolle kann es hierbei passieren, dass das Puzzle trivial (langweilig) oder nicht mehr eindeutig lösbar wird.

Mathematik

Die Zahl der möglichen 9×9-Sudokus beträgt nach Berechnung von Bertram Felgenhauer (im Jahr 2005) 6.670.903.752.021.072.936.960; diese Zahl ist gleich 9! × 72² × 2⁷ × 27.704.267.971; der letzte Faktor ist eine Primzahl. Die Zahl wurde unabhängig davon durch Ed Russell bestätigt. Nach Ed Russel und Frazer Jarvis gibt es 5.472.730.538 Möglichkeiten bei Berücksichtigung von Symmetrien. Die Zahl gültiger 16×16-Sudokus ist unbekannt.

Die maximale Zahl von Vorgaben, die nicht zu einer eindeutigen Lösung führen, ist, unabhängig von der Variante, um vier geringer als die Gesamtzahl der Felder (z. B. 81 - 4 = 77 bei der Standardvariante). Wenn von zwei Zahlen jeweils zwei Vorgaben fehlen, die zugehörigen Felder auf den Ecken eines Rechtecks liegen, dessen Ecken paarweise im selben Block liegen, und dessen Kanten in der selben Zeile bzw. Spalte liegen, gibt es zwei Möglichkeiten, diese Zahlen einzutragen. Das andere Extrem - die Mindestzahl von Vorgaben, die zu einer eindeutigen Lösung führen - ist ein ungelöstes Problem. Die Mindestzahl, die bisher für die Standardvariante ohne Symmetrieforderung gefunden wurde, ist 17. Dies haben japanische Rätselenthusiasten herausgefunden. Bei drehsymmetrischer Anordnung sind es 18.

Quelle: englischer Wikipediaartikel

Hilfen beim Lösen

Die Hilfen zum Lösen eines Sudokus sind nicht normiert. Deshalb werden hier nur Hilfen angeboten, die jeder individuell abändern und verfeinern kann.

Die "Uhrzeigerstrichmethode"

Datei:Sudoku Kandidaten.png

Da die Sudokus in Zeitungen und Magazinen häufig sehr klein abgedruckt sind, ist die Uhrzeigerstrichmethode hilfreich, die Kandidaten für ein Feld festzuhalten. Man macht einfach einen kleinen Strich an der Stelle des "Uhrzeigers" (siehe Bild). Die Fünf stellt eine Ausnahme dar. Sie wird als kleiner Punkt in der Mitte dargestellt. So kann man sich mehrere Kandidaten für ein Feld merken. Wenn man keinen Radiergummi zur Hand hat, kann man einen Kandidatenstrich einfach durchstreichen, wenn weitere Überlegungen diesen ausschließen. Diese Methode ist bei weitem leserlicher als das Schreiben von kleinen Zahlen.

Weblinks

• Sudoku-Generator
• Sudoku-Solver (löst auch schwierige Sudokus)
• Lösungen für Sudokus (deutsch, mit Quellcode)
• Artikel "Verlage entdecken Rätselmarkt" in der Welt am Sonntag vom 19. Juni 2005
• Sudoku als Brettspiel (Übersichtsartikel der Zeitschrift Spielbox)