So generieren Sie ein Sudoku mit eindeutiger Lösung

Ein Sudoku mit eindeutiger Lösung generieren Sie in zwei Schritten. Füllen Sie zuerst ein leeres 9×9-Gitter vollständig, per Backtracking mit Ziffern in zufälliger Reihenfolge. Leeren Sie dann einzelne Felder in zufälliger Reihenfolge und prüfen Sie nach jedem Leeren mit einem Solver, ob das Rätsel noch genau eine Lösung hat. Wenn nicht, setzen Sie die Ziffer zurück. Auf einer gewöhnlichen CPU dauert das im Median weniger als eine Millisekunde.

Das Verfahren passt zu jedem Spiel und jeder App, die beliebig viele neue Rätsel ohne Handarbeit braucht. Ein Beispiel aus der Praxis sind die Sudokus in unserer App mit Kreuzworträtseln und Denkspielen (App Store, Google Play).

#Warum genau eine Lösung

Die Regeln kennt jeder: In jeder Zeile, jeder Spalte und jedem 3×3-Block steht jede Ziffer von 1 bis 9 genau einmal. Seltener wird erwähnt, dass ein gutes Rätsel nur eine Lösung hat. Nur dann lässt es sich mit reiner Logik lösen, ohne Raten.

Das hat auch eine praktische Seite. Ein Spiel speichert meist eine Lösung, prüft damit das Ergebnis und gibt Hinweise. Hat ein Rätsel zwei Lösungen, kann der Spieler bei der anderen landen, die genauso richtig ist, und das Spiel erkennt sie nicht an.

#Schritt 1: Einen schnellen Solver schreiben

Ein Solver ist ein Programm, das das Sudoku löst. Er arbeitet mit Backtracking: Er setzt eine der möglichen Ziffern in ein Feld, geht zum nächsten Feld weiter und kehrt bei einem Widerspruch zurück, um eine andere Ziffer zu probieren. Sie brauchen ihn zweimal: zum Füllen des leeren Gitters und zur Eindeutigkeitsprüfung. Die Prüfung läuft nach jedem geleerten Feld, also 40- bis 70-mal pro Rätsel, und muss deshalb schnell sein. Entscheidend sind zwei Dinge:

• Bitmasken. Speichern Sie für jede Zeile, jede Spalte und jeden Block eine 9-Bit-Zahl mit den bereits verwendeten Ziffern. Die Kandidaten eines Feldes, also die Ziffern, die dort noch stehen dürfen, sind dann eine einzige Operation: alle Ziffern außer denen, die schon in seiner Zeile, Spalte oder seinem Block stehen. Die Anzahl der Kandidaten ist die Zahl der gesetzten Bits und lässt sich vorab in eine Tabelle mit 512 Werten rechnen.
• Zuerst das Feld mit den wenigsten Kandidaten. Nehmen Sie nicht das erste leere Feld von links, sondern das mit den wenigsten Möglichkeiten (in der Literatur die MRV-Heuristik, minimum remaining values). Ein Feld mit nur einem Kandidaten füllen Sie sofort, ein Feld ohne Kandidaten bedeutet einen toten Zweig, und Sie gehen zurück.

Bei schweren Rätseln braucht die Eindeutigkeitsprüfung mit dieser Regel im Median 311 Schritte. Nimmt der Solver die Felder der Reihe nach von links nach rechts, sind es im Median 28.579 Schritte und in den schlechtesten 5 % der Fälle über 300.000. Der Unterschied ist etwa 90-fach.

#Schritt 2: Das ganze Gitter füllen

Ein volles Gitter erhalten Sie mit demselben Solver auf einem leeren Gitter. Der einzige Unterschied: Die Kandidaten eines Feldes probieren Sie in zufälliger Reihenfolge. Die erste gefundene Lösung ist ein zufälliges, gültiges, vollständig gefülltes Gitter.

#Warum zufälliges Leeren nicht reicht

Die einfachste Idee ist, N zufällige Felder des vollen Gitters zu leeren, etwa 40, 50 oder 55 je nach Schwierigkeit. Das Rätsel sieht gut aus, hat aber oft keine eindeutige Lösung.

Das Bild zeigt den typischen Fall. Vier Felder an den Ecken eines Rechtecks, das zwei Blöcke berührt, lassen sich auf zwei Arten füllen, und der Rest des Gitters entscheidet nicht darüber. Sudoku-Löser kennen dieses Muster als Deadly Pattern. Bei 1.000 Rätseln pro Schwierigkeit sieht das Ergebnis so aus:

Ein schweres Rätsel aus zufälligem Leeren hat im Schnitt Hunderte Lösungen. Eine Eindeutigkeitsprüfung nach jedem Leeren ist deshalb nötig.

#Schritt 3: Felder mit Eindeutigkeitsprüfung leeren

Gehen Sie alle 81 Felder in zufälliger Reihenfolge durch. Versuchen Sie, jedes zu leeren, und zählen Sie mit dem Solver die Lösungen, brechen Sie aber bei zwei ab. Mehr müssen Sie nicht wissen: Eine Lösung heißt, das Feld darf leer bleiben, zwei heißen, es muss zurück.

rätsel = Kopie des vollen Gitters
geleert = 0
für jedes Feld in zufälliger Reihenfolge:
    wenn geleert == ziel: Ende
    ziffer = rätsel[feld]
    rätsel[feld] = leer
    wenn anzahl_lösungen(rätsel, höchstens 2) == 1:
        geleert = geleert + 1
    sonst:
        rätsel[feld] = ziffer

Ein Feld, das Sie einmal zurückgesetzt haben, probieren Sie nicht noch einmal. Weiteres Leeren lockert das Rätsel nur, ein Feld, das sich jetzt nicht leeren lässt, lässt sich also auch später nicht leeren.

#Schritt 4: Schwierigkeit über die Zahl leerer Felder einstellen

Das einfachste Maß für die Schwierigkeit ist die Zahl der geleerten Felder. Die drei Stufen, die wir in unserem Spiel verwenden:

Je weniger Ziffern übrig sind, desto öfter würde ein weiteres Leeren die Eindeutigkeit zerstören, und das Feld muss zurück. Auf der schweren Stufe bleibt ein einzelner Durchlauf manchmal stehen, bevor er 55 leere Felder erreicht. Generieren Sie dann ein neues volles Gitter und versuchen Sie es erneut. Bei einer Messung an 1.000 schweren Rätseln reichte der erste Durchlauf in 97,6 % der Fälle, und es waren nie mehr als 3 Versuche nötig.

#Geschwindigkeit und Zuverlässigkeit des Generators

Wir haben den Generator an 1.000 Rätseln pro Schwierigkeit laufen lassen (Node.js 22 auf einer Server-CPU, ein Telefon ist langsamer):

Zusätzlich haben wir jedes generierte Rätsel unabhängig mit dem Solver geprüft. Alle 3.000 hatten eine einzige Lösung.

#Wo die Zahl leerer Felder nicht ausreicht

Die Zahl der vorgegebenen Ziffern ist ein grobes Maß für die Schwierigkeit. Zwei Rätsel mit 26 Ziffern können unterschiedlich schwer sein, je nachdem, welche Lösungstechniken sie verlangen. Eine genauere Bewertung würde das Rätsel wie ein Mensch lösen und die schwierigste Technik festhalten, die nötig war. Für ein Handyspiel, in dem der Spieler aus drei Stufen wählt, genügt die Zahl der vorgegebenen Ziffern.

Wenn Sie ein ähnliches Problem lösen, Rätsel generieren oder eine mobile App brauchen, schreiben Sie uns. Wie man ein Wortsuchrätsel mit Lösungswort generiert, beschreibt eine eigene Anleitung. Dem Schwedenrätsel mit Lösungswort widmet sich eine weitere Anleitung.