Wie Computer Sudoku lösen

Der klassische Algorithmus füllt die erste leere Zelle mit der niedrigsten zulässigen Ziffer, geht weiter und weicht bei jeder Sackgasse zurück, um die nächste Ziffer zu probieren. Mit der offensichtlichen Buchhaltung (immer zuerst die am stärksten eingeschränkte Zelle) kollabiert jedes 9×9-Sudoku in Millisekunden.

Backtracking beantwortet „Wie lautet die Lösung?“ und, ebenso wichtig, „Wie viele Lösungen gibt es?“: Lass die Suche über den ersten Treffer hinauslaufen und sieh nach, ob ein zweiter existiert. Dieser Eindeutigkeits-Check ist das Rückgrat der Rätsel-Generierung, und der Grund, warum Techniken wie das Unique Rectangle überhaupt sicher anwendbar sind.

Unser zweiter Löser kennt denselben Technik-Katalog, den du hier lernen kannst, geordnet von trivial bis heftig. In jeder Stellung fragt er: Was ist die einfachste Technik, die Fortschritt bringt? Das Ergebnis ist nicht nur eine Lösung, sondern ein Lösungsweg: eine menschenförmige Erklärung des Rätsels.

Dieser Weg treibt fast alles auf dieser Seite an: Das Hinweis-System zeigt dir seinen nächsten Schritt statt einer blanken Ziffer, der Bewerter liest die härteste Technik des Wegs für die Stufen-Einordnung, und der Drill-Generator erntet seine Stellungen als Übungsmaterial.

Neue Rätsel beginnen als voll gelöstes Gitter aus randomisiertem Backtracking. Der Generator gräbt dann Zelle für Zelle aus, und nach jeder Entnahme prüft der Backtracking-Löser, ob das Rätsel noch genau eine Lösung hat: wenn nicht, kommt die Zelle zurück.

Das ausgegrabene Rätsel trifft dann auf den Technik-Löser, der über sein Schicksal entscheidet: bewerten, in eine Kampagnen-Stufe einsortieren oder als jenseits des Katalogs verwerfen. Vorschlaghammer für Konstruktion und Gewissheit, Lehrer fürs Urteil: mit dieser Arbeitsteilung funktioniert im Kern jede ernsthafte Sudoku-App.