Das Knobelspiel Sudoku ("einsame Zahlen") eroberte vor etlichen Jahren von Japan aus die Welt und hat auch nach dem Abflauen der ersten Begeisterungswoge immer noch einen festen Platz in Tageszeitungen und auf Internetseiten. Es geht darum, ein quadratisches Brett aus 9 mal 9 Feldern so mit den Zahlen von 1 bis 9 zu füllen, dass jede der Zahlen in jeder Zeile, jeder Spalte und in jedem Teilkästchen der Größe 3  · 3 genau einmal vorkommt (Spektrum der Wissenschaft 3/2006, S. 100). Die Belegung gewisser Felder ist vorgegeben.

Ein Sudoku-Rätsel ist nur dann richtig gestellt, wenn diese Vorgaben die Lösung eindeutig bestimmen. Es darf also zu ein und derselben Vorgabemenge keine zwei vollständig und regelgerecht ausgefüllte Sudoku-Bretter geben.

Weit entfernt von dem kreuzworträtselartigen Zeitvertreib aus der Tageszeitung wetteifern die harten Sudoku- Profis darum, aus möglichst wenigen Vorgaben die komplette Belegung zu erschließen. Im Prinzip ist ein Rätsel umso schwerer, je weniger Information es bereitstellt. Die härtesten unter ihnen fordern vom Löser, aus nur 17 Vorgaben zu erschließen, was in die restlichen 64 Felder gehört…