TeX diesmal rätselhaft: Sudoku

P. Zimmermann

Hätten Sie gedacht, dass der Begriff "Sudoku" zu den Top 10 Suchbegriffen von Google im Jahr 2005 gehörte? Was verbirgt sich hinter Sudoku? Was hat TeX damit zu tun?

LaTeX und Sudoku

Was ist Sudoku überhaupt?

Sudoku wurde vermutlich das erste Mal um 1970 in New York vom Rätselspezialisten Dell in seinem Magazin "Mathematische Rätsel und logische Probleme" veröffentlicht.

Die eigentliche Geburtsstunde fällt wohl in das Jahr 1984, in dem die japanische Zeitschrift "Monthly Nikolist" das Rätsel unter dem Namen Suji wa dokushin ni kagiru - daraus abgeleitet der Name Su (= Nummer) doku (= einzeln) - regelmäßig abdruckte. Der Neuseeländer Wayne Gould entdeckte es auf einer Japanreise und entwickelte eine Software zur Generierung von Sudokus. Er bot seine Rätsel der Times in London an, die am 12. November 2004 erstmals ein Rätsel veröffentlichte und damit eine Sudoku-Lawine in der westlichen Welt auslöste. Inzwischen finden sich Sudokus in vielen deutschen Printmedien.

Wie funktioniert Sudoku?

Ein Sudoku-Rätsel besteht aus einem Raster mit 9×9 Feldern und Zahlen von "1" bis "9" in einigen der Felder. Das Problem besteht nun darin, alle leeren Felder so zu füllen, dass in jeder Spalte und Zeile und in jedem der neun 3×3-Quadrate, aus denen das Rätsel zusammengesetzt ist, alle Zahlen von "1" bis "9" stehen. Verwenden Sie am besten Bleistift und Radiergummi. Für jedes Rätsel gibt es nur eine Lösung.

Was hat TeX mit Sudoku zu tun?

Das erste LaTeX-Paket Sudoku zur Ausgabe von Sudokus datiert auf den Peter und Paul Tag aus dem Jahr 2005 und stammt von Paul Abraham. Neben Ausgabegrößen- und Zeichensatzwahl werden Sudokus in einer sudoku-Umgebung spezifiziert.

Eine Parallelentwicklung von Peter Wilson hat im Februar diesen Jahres zu einem Paket "Sudoku Bundle" geführt, das neben der Ausgabe von Sudokus auch deren automatische Erzeugung und Lösung durch TeX ermöglicht. Zusätzlich liegen 50 Rätsel als Beispiele bei. Die Ausgabe, Erzeugung und Lösung erfolgt über eine Hilfsdatei, die das Schema eines Sudokurätsels in Form von neun Zeilen zu je neun Spalten enthält. Als Beispieldatei betrachte man etwa leicht.sud mit den Eingabedaten für obiges Rätsel:

.7.1.365.
5.67..3.1
2..4.6.87
.81....65
.........
3.4...1.8
43.6.8.1.
1.23.5...
.68..2.4.

Fehlende Zahlenwerte markiert ein Punkt. Texteingaben nach den Zahlen- und Punktwerten können als Kommentare dienen. Zur Ausgabe ist das Paket Printsudoku erforderlich:

\usepackage{printsudoku}
\sudoku{leicht.sud}

Das Einlesen und Ausgeben übernimmt dann ein \sudoku"=Kommando mit der Datei als Argument. Über \cluefont und \cellsize lässt sich das Layout des Rätsels abändern. Voreingestellt ist \Huge beim Zeichensatz und 2.5\baselineskip bei der Feldgröße; die Ausgabe der Sudokus dieses Artikels ist durch folgende Einstellung festgelegt:

\cluefont{\LARGE}
\cellsize{1.5\baselineskip}

Zur Lösung von Sudokus dient das Paket Solvesudoku. Hier wird die Rechenfähigkeit von TeX herangezogen, um aus einem vorgegebenen Rätsel ein ausgefülltes 9×9-Feld zu generieren.

Ein
\sudokusolve{leicht.sud}
gibt zunächst unter Einbeziehung des Pakets Printsudoku das Rätsel aus und versucht anschließend eine Lösung zu errechnen. In kleinerer Schrift wird die Lösung (bzw. soviele Werte errechnet werden konnten) unter das Rätsel gedruckt. Am Ende dieses Artikels finden Sie solche Lösungen zu den vorgestellten Rätseln.

Wenn TeX Sudokus lösen kann, kann TeX auch Sudokus generieren. Dazu liegt das Paket Create-sudoku bereit, das unter Einbeziehung des Pakets Random Zufallszahlen erzeugt und in das Sudokufeld einträgt.

\usepackage{createsudoku}
\generategrid

Zunächst füllt das \generategrid ein Sudokufeld mit Zufallszahlen und entfernt dann nach und nach wieder Werte solange bis durch \sudokusolve keine Lösung mehr produziert werden kann. Das Rätsel und die Lösung werden gesetzt. Zusätzlich stehen die Eingabedaten für das Rätsel in der Datendatei gensud.sud (9×9 Feld).

Die Zufallszahlen errechnen sich aus dem aktuellen Datum und Uhrzeit. Sie können aber auch mit dem Kommando \setsudrandom{wert} von einem fest vorgegebenen Wert aus bestimmt werden.
\setsudrandom{1508763317}
Der Wert ist aus einem Bereich -1 ≤ wert ≤ 2 147 483 646 zu wählen. Der angegebene Beispielwert dient zur Anfertigung des Rätsels Leicht. -1 greift auf Datum und Uhrzeit zurück, mit der Folge, dass stets ein neues, verändertes Rätsel produziert wird. Zur Variation der Rätsel lassen sich Parameter einsetzen: \elimseventeen (17 Zahlen zusätzlich entfernen), \elimcross und \elimex (keine Zahlen in der Feldmitte bzw. den Diagonalen), \elimcrossandnines (zusätzlich keine "9") und \elimcrossandexandnines. Das Rätsel Moderat basiert auf den Einstellungen:

\setsudrandom{11111113}
\elimseventeen

Das Rätsel Schwer entstammt der Zeitung Daily Telegraph vom Sonntag, dem 26. Februar 2006.

Beide Pakete zu Sudoku sind Bestandteil der MiKTeX-Verteilung. Weitere Informationen zu Sudokus finden sich neben anderen im Web unter http://sudoku.zeit.de/sudoku/kunden/die_zeit/ oder http://www.sudoku.org.uk.

Lösungen zu den obigen Sudokus: