Wie Computer Sudoku lösen

Computer können normale 9×9-Sudoku extrem schnell lösen, aber es gibt nicht den einen „Sudoku-Algorithmus“. Unterschiedliche Solver sind für unterschiedliche Aufgaben gebaut.

Ein vollständiger Solver versucht festzustellen, ob ein Rätsel null, genau eine oder mehrere Lösungen besitzt.

Ein Human-Style-Solver versucht dagegen, das Rätsel mit benannten logischen Techniken in einer sinnvollen Reihenfolge zu erklären.

Generator, Validator und Difficulty Rater können beide Arten gleichzeitig benötigen.

Sudoku als Constraint-Problem

Für jede Zelle verwaltet das Programm eine Menge möglicher Ziffern.

Die Constraints verlangen:

• genau eine Ziffer pro Zelle;
• jede Ziffer einmal pro Zeile;
• jede Ziffer einmal pro Spalte;
• jede Ziffer einmal pro Block.

Wird ein Wert festgelegt, können inkompatible Werte an anderer Stelle entfernt werden. Das ist Constraint Propagation – das rechnerische Gegenstück zum Aktualisieren von Kandidaten nach einer menschlichen Platzierung.

Kandidatenpropagation

Ein einfacher Solver kann wiederholt:

1. legale Kandidaten berechnen;
2. erzwungene Zellen setzen;
3. durch neue Platzierungen blockierte Kandidaten entfernen;
4. wiederholen, bis kein direkter Fortschritt mehr möglich ist.

Das löst leichte Rätsel, aber nicht jedes gültige Sudoku.

Ein vollständiger Solver braucht daher eine Methode, Alternativen systematisch zu untersuchen, wenn reine Propagation stoppt.

Backtracking

Backtracking ist einer der einfachsten vollständigen Ansätze.

1. eine ungelöste Zelle auswählen;
2. einen legalen Kandidaten ausprobieren;
3. Constraints propagieren;
4. bei einem Widerspruch die Wahl zurücknehmen;
5. den nächsten Kandidaten versuchen;
6. fortfahren, bis ein vollständiges Grid gefunden wurde oder alle Alternativen scheitern.

Gute Implementierungen wählen zuerst besonders stark eingeschränkte Zellen, um die Verzweigung klein zu halten.

Backtracking ist nicht dasselbe wie die Art, wie VeyraPlay Menschen Sudoku beibringt. Es ist eine effiziente Suchmethode für Maschinen.

Lösungen zählen

Um Eindeutigkeit zu validieren, darf ein Solver nicht einfach nach der ersten gefundenen Lösung stoppen.

Er kann weitersuchen, bis:

• keine Lösung existiert;
• genau eine Lösung bewiesen ist;
• oder eine zweite Lösung gefunden wird – das reicht bereits, um Nicht-Eindeutigkeit zu beweisen.

Diese Fähigkeit ist zentral für Generierung und für die sichere Verwendung von Eindeutigkeitstechniken.

Sudoku als Exact Cover

Klassisches 9×9-Sudoku lässt sich als Exact-Cover-Problem modellieren.

Es gibt vier Gruppen von Bedingungen:

• 81 Zellbedingungen: jede Zelle erhält genau einen Wert;
• 81 Zeile-Ziffer-Bedingungen;
• 81 Spalte-Ziffer-Bedingungen;
• 81 Block-Ziffer-Bedingungen.

Insgesamt:

81 × 4 = 324 Bedingungen

Es gibt 729 mögliche Zeile/Spalte/Ziffer-Zuordnungen:

9 × 9 × 9 = 729 mögliche Platzierungen

Jede mögliche Platzierung erfüllt genau vier passende Bedingungen.

Die Aufgabe wird damit zu: Wähle Zuordnungszeilen so aus, dass jede der 324 Bedingungen genau einmal abgedeckt ist.

Algorithm X

Donald Knuths Algorithm X ist ein rekursives Verfahren für Exact-Cover-Probleme.

In jedem Schritt:

1. wählt er eine noch nicht abgedeckte Bedingung;
2. wählt eine Kandidatenzeile, die sie erfüllt;
3. deckt kollidierende Bedingungen und Zeilen ab;
4. ruft sich rekursiv auf;
5. geht bei Bedarf per Backtracking zurück.

Dasselbe Verfahren kann eine einzelne Sudoku-Lösung finden oder genügend Lösungen enumerieren, um Eindeutigkeit zu prüfen.

Dancing Links (DLX)

Dancing Links ist eine effiziente Datenstruktur bzw. Implementierungstechnik für Algorithm X auf dünn besetzten Matrizen.

Die 729×324-Exact-Cover-Matrix von Sudoku ist sparse: Jede mögliche Platzierung berührt nur vier Bedingungen.

DLX macht das Entfernen und Wiederherstellen dieser Beziehungen während rekursiver Suche besonders effizient.

Algorithm X ist die Suchidee; Dancing Links ist eine bekannte Technik, um deren Cover/Uncover-Operationen umzusetzen.

Constraint Programming und SAT-artige Modelle

Sudoku kann außerdem für allgemeine Solver formuliert werden, zum Beispiel als:

• Constraint Satisfaction / Constraint Programming (CSP/CP);
• SAT- bzw. Boolesche Kodierung;
• Integer Programming;
• Graph- oder Exact-Cover-Modell.

Welche Darstellung am besten ist, hängt vom Ziel ab: maximale Geschwindigkeit, Erklärbarkeit, Lösungszählung, Erweiterbarkeit auf Varianten oder Forschungsanalyse.

Human-Style-Solver

Ein Human-Style-Solver sucht nach benannten Deduktionen wie:

• Singles;
• Locked Candidates;
• Subsets;
• Fish;
• Wings;
• Coloring;
• Chains;
• ALS.

Er fragt nicht nur „finde ich eine Lösung?“, sondern zeichnet einen Lösungsweg auf.

Dieser Lösungsweg kann verwendet werden für:

• Hinweise;
• Tutorials;
• Difficulty Rating;
• Qualitätsfilter im Generator;
• die Frage, welche Technik ein Rätsel wirklich freischaltet.

Warum vollständige und Human-Style-Solver getrennt sein sollten

Ein Rätsel kann für Backtracking trivial und für einen Menschen sehr schwer sein.

Maschineller Suchaufwand entspricht nicht direkt der menschlichen Erkennungsschwierigkeit.

Eine robuste Sudoku-Plattform kann deshalb trennen:

• vollständiger Solver → Gültigkeit und Lösungsanzahl;
• Human Solver → Erklärung und Rating;
• Generator → Erzeugung möglicher Rätsel;
• Analyzer → Metadaten und Qualitätschecks.

Wie ein Generator Solver verwendet

Wenn Vorgaben aus einem vollständigen Lösungsgitter entfernt werden, prüft ein vollständiger Solver zunächst, ob Eindeutigkeit erhalten bleibt.

Danach kann ein Human-Style-Solver fragen:

• ist das Rätsel mit dem erlaubten Technikset logisch lösbar?
• welche schwierigste Technik ist erforderlich?
• wie viele Schritte werden benötigt?
• wo liegen die Bottlenecks?
• erscheint die beabsichtigte Technik tatsächlich im Lösungsweg?

Darum bedeutet „ein Sudoku generieren“ wesentlich mehr als „zufällig Ziffern löschen“.

Raten Computer?

Suchalgorithmen untersuchen Alternativen, doch „Raten“ ist dafür technisch kein besonders hilfreicher Begriff.

Ein vollständiger Backtracking-Solver enumeriert einen endlichen Suchraum systematisch, beschneidet ihn durch Constraints und beweist Ergebnisse durch vollständige Ausschöpfung.

Eine Human-Guide über Raten beschäftigt sich dagegen mit unsupported commitments eines Spielers beim Lösen. Das sind zwei verschiedene Kontexte.

FAQ

Was ist der schnellste Algorithmus für Sudoku?

Es gibt keine universelle Antwort. Für 9×9-Sudoku sind optimiertes Backtracking, Exact Cover/DLX und Constraint Solver alle extrem schnell. Die Wahl hängt von Aufgabe und Implementierung ab.

Was sind die 324 Exact-Cover-Bedingungen?

81 Zellbedingungen plus je 81 Zeile-Ziffer-, Spalte-Ziffer- und Block-Ziffer-Bedingungen.

Warum gibt es 729 Kandidatenzeilen?

Weil es 9 Zeilen × 9 Spalten × 9 mögliche Ziffern gibt – eine Zeile im Exact-Cover-Modell für jede mögliche Platzierung.

Ist Algorithm X dasselbe wie Dancing Links?

Nein. Algorithm X ist der rekursive Exact-Cover-Algorithmus; Dancing Links ist eine Datenstrukturtechnik, die häufig für effiziente Cover/Uncover-Operationen genutzt wird.

Verwenden menschliche Sudoku-Solver Backtracking?

Human-Style-Logiksolver vermeiden es normalerweise, weil ihr Ziel ein erklärbarer Deduktionsweg ist. Vollständige Validatoren verwenden Suchverfahren dagegen häufig.

Was du als Nächstes lernen solltest

Lies die Guide zur Generierung, um Validatoren und Human Solver in der Puzzle-Pipeline einzuordnen, oder „Wie man ein Sudoku erstellt“ für den praktischen Konstruktionsprozess.