Wie Sudokus erzeugt werden: die Technik hinter jedem Spielfeld

Von Miguel Arechaga

Jedes Mal, wenn du auf „neues Sudoku“ drückst, erscheint ein anderes, ausgewogenes Spielfeld mit einer eindeutigen Lösung. Das kann wie Magie wirken, aber dahinter steckt ein sehr eleganter logischer Prozess, den jeder verstehen kann, ohne programmieren zu können. In diesem Artikel führe ich dich Schritt für Schritt und in einfachen Worten durch die Frage, wie ein Computer ein Sudoku von Grund auf baut und dafür sorgt, dass es fair und lösbar ist.

Schritt 1: ein vollständiges, gültiges Gitter aufbauen

Anders als viele es sich vorstellen, beginnt ein Generator nicht damit, einzelne Vorgaben zu setzen. Er fängt andersherum an: indem er ein ganzes Neun-mal-neun-Spielfeld füllt, alle 81 Zahlen an ihrem Platz, unter Beachtung aller Regeln. Dazu geht er Feld für Feld vor, probiert zufällige Zahlen aus und prüft, dass sie keine Zeilen-, Spalten- oder Blockbedingung verletzen. Wenn ihm irgendwann die gültigen Möglichkeiten ausgehen, geht er zurück und probiert eine andere Kombination. Diese Technik des „Probierens und Zurückgehens“ heißt Backtracking, und sie garantiert am Ende ein perfekt regelkonformes, vollständiges Gitter. Dieses Gitter wird zur Lösung des künftigen Sudokus.

Schritt 2: Zahlen entfernen, ohne die eindeutige Lösung zu verlieren

Ist das Spielfeld voll, beginnt der Generator, Zahlen eine nach der anderen in zufälliger Reihenfolge zu löschen. Aber er löscht nicht willkürlich: Jedes Mal, wenn er eine Ziffer entfernt, prüft er eine heilige Bedingung. Das Sudoku, das übrig bleibt, muss weiterhin genau eine mögliche Lösung haben. Wenn das Löschen einer Zahl dazu führt, dass das Spielfeld zwei oder mehr Wege zulässt, es zu vervollständigen, kommt diese Ziffer zurück an ihren Platz und stattdessen wird eine andere ausprobiert. Diese Prüfung ist es, die ein echtes Sudoku von einem bloßen Haufen Felder unterscheidet: Ein gutes Sudoku zwingt dich nie zum Raten, denn es gibt nur einen logischen Weg bis ins Ziel.

Das Herz des Systems: Lösungen zählen

Alles hängt also davon ab, eine Frage schnell beantworten zu können: „Hat dieses Spielfeld eine einzige Lösung oder mehr als eine?“ Dafür benutzt der Generator einen kleinen internen Löser, der versucht, das Rätsel zu lösen, und zählt, wie viele verschiedene Lösungen er findet. Sobald er eine zweite entdeckt, hört er auf, denn er weiß bereits, dass diese Lücke nicht leer bleiben kann. Das effizient zu tun, ist der Schlüssel dazu, die Erzeugung augenblicklich zu machen, und es gelingt mit Tricks wie dem, immer das Feld mit den wenigsten Möglichkeiten zu wählen, um die Analyse zu beschleunigen.

Wie der Schwierigkeitsgrad kalibriert wird

Hier eine Idee, die viele überrascht: Die Schwierigkeit eines Sudokus hängt nicht nur davon ab, wie viele Zahlen sichtbar bleiben. Das spielt schon eine Rolle, ja (ein Spielfeld mit mehr Lücken ist tendenziell schwerer), aber was das Niveau wirklich bestimmt, ist welche Art von Überlegung zum Lösen nötig ist. Ein leichtes Sudoku lässt sich mit einfachem Abscannen vervollständigen; ein Expertenrätsel kann Techniken wie versteckte Paare oder X-Wing erfordern. Deshalb zählen Generatoren nicht einfach nur Vorgaben: Sie streben pro Niveau eine ungefähre Zahl sichtbarer Felder an und verlassen sich darauf, dass sich bei so vielen Lücken die für jeden Schwierigkeitsgrad typischen Situationen einstellen. Es ist ein Gleichgewicht zwischen der Frage, wie viele Zahlen stehen bleiben und welche logischen Herausforderungen ausgelöst werden.

Warum sie sich nie wiederholen

Da jede Partie von einem anderen, zufällig erzeugten vollständigen Gitter ausgeht, sind die möglichen Kombinationen astronomisch: Es gibt Milliarden und Abermilliarden im Wesentlichen verschiedener Sudokus. In der Praxis bedeutet das, dass du selbst bei Tausenden von Partien nie zweimal genau dasselbe Spielfeld bekommen würdest. Das ist der große Vorteil der Erzeugung per Computer gegenüber gedruckten Büchern: eine buchstäblich endlose Quelle von Rätseln, jedes davon neu und geprüft.

Wie die Spielfelder von MundoSudoku funktionieren

Alles, was du gerade gelesen hast, ist genau das, was bei MundoSudoku unter der Haube passiert, jedes Mal, wenn du eine Partie startest: Es wird ein vollständiges Gitter aufgebaut, Felder werden geleert, wobei bei jedem Schritt geprüft wird, dass die Lösung eindeutig bleibt, und die Anzahl der Vorgaben wird an das von dir gewählte Niveau angepasst. Deshalb kannst du spielen im Wissen, dass sich jedes Spielfeld, so schwer es auch sein mag, immer mit reiner Logik und ohne Raten lösen lässt. Und wenn dich die Geschichte hinter all dem neugierig macht, wirf einen Blick auf die Geschichte des Sudoku, wo wir beschreiben, wie es vom Papier zu den automatischen Generatoren kam.