Ein Sudoku-Rätsel entsteht, indem man aus einem fertig ausgefüllten Brett, der Lösung, Zahlen löscht. Wie viele fertig ausgefüllte Bretter, die den Regeln entsprechen, gibt es eigentlich insgesamt?
Ein 4×4-Brett gibt es 288-mal
Fangen wir mit dem kleinsten Brett an, 4×4 (Blöcke aus 2×2 Feldern, Zahlen 1 bis 4). Hier ein Beispiel.
In jeder Spalte, Zeile und jedem Block steht jede Zahl von 1 bis 4 genau einmal. Als ein Computer alle solchen Bretter einzeln durchzählte, kam er auf 288.
Mit festgelegter erster Zeile zählt es sich leichter
Du musst nicht alles abzählen. Es gibt einen klugen Weg, die Menge zu verkleinern.
Wenn du bei einem fertigen Brett die Zahlen umbenennst, zum Beispiel „1 und 2 vertauschen“, ist es immer noch ein fertiges Brett. Ein Brett mit der ersten Zeile „2 1 3 4“ wird zu einem Brett mit der ersten Zeile „1 2 3 4“, wenn du 1 und 2 vertauschst. Es genügt also,
- nur die Bretter mit der ersten Zeile „1 2 3 4“ zu zählen und
- das mit der Zahl der Möglichkeiten für die erste Zeile (4×3×2×1 = 24) zu multiplizieren.
Schon hast du die Gesamtzahl. Bei 4×4 gibt es 12 Bretter mit der ersten Zeile „1 2 3 4“, und 12 × 24 = 288.
Ein 6×6-Brett gibt es 28.200.960-mal
Das ist dasselbe Brett wie das 6×6 Mini der App NumberPlace, mit Blöcken aus 2 Zeilen × 3 Spalten. Mit derselben Methode, also der ersten Zeile „1 2 3 4 5 6“ und dem Zählen der Bretter, kommst du auf 39.168. Die erste Zeile lässt sich auf 6×5×4×3×2×1 = 720 Arten anordnen, also
39.168 × 720 = 28.200.960
Es sind also 28.200.960 (rund 28,2 Millionen). Das ist etwa das 100.000-Fache von 4×4.
Ein 9×9-Brett gibt es etwa 6,67 × 10²¹-mal
Die Zahl der fertigen 9×9-Bretter beträgt
6.670.903.752.021.072.936.960
also etwa 6,67 × 10²¹ (rund 6,7 Trilliarden). Mitte der 2000er-Jahre wurde sie ermittelt, indem man das Brett in Bänder und Blöcke aufteilte, die Fälle durchging und mit Computern zählte. Selbst wenn du hundert Millionen pro Sekunde zählen würdest, würde es mehr als zwei Millionen Jahre dauern.
Darunter sind viele, die gleich aussehen und sich nur dadurch unterscheiden, dass man das Brett dreht oder spiegelt oder die Zahlen umbenennt. Betrachtet man Bretter, die sich nur im Aussehen unterscheiden, als gleich, sinkt die Zahl auf etwa 5,5 Milliarden.
Rätsel gibt es noch viel mehr
Aus einem einzigen fertigen Brett kannst du viele verschiedene Rätsel machen, je nachdem, welche Zahlen du löschst. Die App NumberPlace erzeugt jedes Mal frisch ein neues fertiges Brett und löscht daraus Zahlen, um ein Rätsel zu bauen (So erstellst du ein Sudoku). Du wirst kaum zweimal auf dasselbe Rätsel treffen.
Wie viele Zahlen du stehen lassen musst, damit die Lösung eindeutig ist, steht in Wie viele Vorgaben braucht ein Sudoku mindestens?.
