Minimale Sudokus
Vermutlich müssen in einem Sudoku mindestens 17 Zahlen vorgegeben sein.
Wenn man aus einem bestehenden, eindeutigen Sudoku Zahlen entfernt, so kann es sein, dass es mehrere Lösungen für dieses neue Sudoku gibt - man sagt, es ist nicht mehr eindeutig.
Man hat bereits sehr viele (über 30.000) Sudoku gefunden, die aus nur 17 vorgegebenen Zahlen bestehen.
Jetzt kann man anfangen, bei jedem dieser Sudoku nacheinander eine Zahl wegzunehmen. Das entstehende Sudoku kann man darauf überprüfen, ob es eindeutig lösbar ist. Bisher hat man noch keines gefunden, das mit nur 16 Zahlen eindeutig ist.
Die Anzahl der Vorgaben für ein minimales Sudoku hängt natürlich von der Größe des Felds ab, das bisher gesagte gilt für normale 9x9-Felder.
Im Allgemeinen nimmt die Zahl ab, wenn man weitere Beschränkungen einführt, wie das z.B. beim sogenannten Killer-Sudoku der Fall ist.
Wie generierte man minimale Sudokus?
Wenn man mit einem normalen Algorithmus Sudokus generiert, und hofft dass manchmal welche mit nur 17 Vorgaben dabei sind, muss man lange warten. Sehr lange. Nach mehreren Tagen hat man meistens immer noch keines gefunden.
Daher muss man anders an das Problem herangehen:
Jede Zahl, die man in ein leeres Feld eingügt, über Einschränkungen auf andere Felder auf: auf alle 8 anderen innerhalb des gleichen 3x3-Blocks, sowie auf den Rest der Zeile und Spalte, insgesamt 8 + 2*6 = 20, sowie auf das Feld selbst: die anderen acht Zahlen können dort nicht mehr sein.
Damit übt jede Zahl also 8 + 20 = 28 Einschränkungen aus.
Wenn man nach minimalen Sudokus sucht, muß man also darauf achten die Zahlen so zu setzen, dass sich die Einschränkungen, die die einzelnen Zahlen auf die Umgebung ausüben, möglichst wenig überlappen.
Um das ganze noch mit einem Beispiel zu verdeutlichen: wenn die ersten drei Zeilen vollständig mit Zahlen gefüllt sind, ist damit der Rest des Sudokus noch lange nicht bestimmt. Sind die Zahlen aber einigermaßen gleichmäßig im ganzen Gitter verteilt, ist es kein Problem, aus 27 Vorgaben ein eindeutiges Sudoku zu bauen.
Ein Generator für minimale Sudokus sortiert also Ansätze mit hohem Überlappungsgrad der einzlenen Zahlen früh aus, um Rechenleistung zu sparen.
Andere Ansätze sind z.B. evolutionäre Algorithmen, die bestehende minimale Sudokus zufällig modifizieren und darauf hoffen, dass sie ein neues finden.
topResourcen
Gordon Royle hat auf seiner Webseite eine umfangreiche Sammlung minimaler Sudokus (englisch).
Minimale Sudokus kann man hier online spielen und als PDF herunterladen (beides auch auf sudokugarden.de).