Constraint-Propagation
Jede Zelle hat eine Kandidatenmenge {1..9}. Eine Zahl in einer Zelle entfernt sie aus Zeile, Spalte und 3×3-Block. Wenn nur ein Kandidat bleibt, ist die Zelle gelöst. Wiederhole bis nichts mehr passiert.
Wenn Propagation nicht reicht
Manche Puzzles erfordern Vermutungen. Backtracking: wähle die Zelle mit den wenigsten Kandidaten, probiere einen aus, propagiere weiter. Schlägt fehl? Zurück und nächsten probieren.
Dancing Links (DLX)
Knuths Algorithmus X modelliert Sudoku als Exact-Cover-Problem: 729 mögliche (Zelle, Wert)-Tupel, 324 Bedingungen. Dancing Links findet die Auswahl, die jede Bedingung genau einmal erfüllt. Löst die härtesten Puzzles in Mikrosekunden.
Lehren fürs Spieldesign
Puzzles, die nur Constraint-Propagation brauchen, fühlen sich logisch an. Puzzles, die Vermutungen erzwingen, fühlen sich frustrierend an. Gute Puzzle-Designer prüfen die Lösbarkeit ohne Vermutungen — die gleiche Disziplin macht Signal//Lock-Level fair.