Die zweitschönste Nebensache der Welt

Dies ist das angekündigte Beispiel zur Aussage:

Die Anzahl der vorbelegten Felder eines Sudokus sagt wenig über die Beschwerlichkeit seines Lösungsweges aus.

Man nehme hierzu das zweite Sudoku in "Mit Muster". Wie man leicht zählt sind 28 Felder bereits vorgegeben, der Rest kann mit den einfachsten "logischen" Methoden gelöst werden. Der recht hohe SSbL-Score von 110 ("hard") ist ein Ergebnis der letztendlich spärlichen Vorbesetzung.

Und nun dies:


Gleiches Muster, gleiche Anzahl belegter Felder. Sollte doch ebenso einfach zu lösen sein.

Viel Spaß!

Jeder, der Sudokus löst, kennt das. So wird gemeinhin beschrieben, wie beschwerlich der Weg zur Lösung eines Sudokus ist.

Doch Vorsicht, hier wird oft mit unterschiedlichem Maß gemessen.

Mein erstes Sudoku-Buch ("Sudoku", Fischer Taschenbuch Verlag) klassifizierte den Schwierigkeitsgrad gemäß der Anzahl der vorgegebenen Felder: 48, 32, 24, das war leicht, mittel und schwer. Ich halte diese Art der Einteilung für unangemessen. Denn man wird leicht Sudokus finden, die die gleiche Anzahl Vorbesetzungen haben, aber unterschiedlich "schwierig" zu lösen sind (ein Beispiel hierzu später).

Der "Sudoku Solver by Logic" nutzt zur Beurteilung der Lösbarkeit eines Sudokus schon nachvollziehbarere Kriterien: Es werden einige "logische" Methoden definiert, mit denen der menschliche Löser normalerweise ein Sudoku löst bzw. lösen kann. Diese Methoden sind unterschiedlich kompliziert in ihrer Anwendung, jede Methode erhält daher einen individuellen "Difficulty Score".

Zur Lösung eines Sudokus werden die einzelnen "logischen" Methoden mit unterschiedlicher Häufigkeit angewandt. Der "Score" für ein Sudoku ergibt sich aus der Summe der "Difficulty Score" aller angewandter Methoden, bei mehrfacher Anwendung geht " Difficulty Score" einer Methode entsprechend häufig in den "Score" ein.

Diesen "Score" eines Sudokus habe ich bereits "SSbL -Score" genannt und werde es auch weiterhin tun.

Die zwei Sudokus, die täglich von einer hier nicht nennbaren Tageszeitung veröffentlich werden, fallen durch ihre symmetischen Muster auf. Z.B. solch eines:


Das Muster ist geklaut, das Sudoku habe ich mit nun fester Vorgabe einer Maske generieren lassen. Aufgrund dieses Musters erhielt das Rätsel einem ärmlichen SSbL-Score von 47 - "easy". Zu einfach.

Hier ein spartanischeres Muster, auch abgeschrieben aus besagter Zeitung, das Sudoku stammt aus meinem Generator:

Dieses Sudoku enthält nun keine systematischen Muster - hoffe ich:


... und so kam es zustande:

Das verbesserte erste Sudoku sah schon ganz gut aus, hat aber noch eine systematische Macke. Diese Macke ist kein Zufall, sondern jedes Sudoku, das wie beschrieben produziert wird hat diesen genetischen Fehler: In den Zeilen der mittleren Blöcke stehen stets "Drillinge".

Das liegt an zweierlei:

An der Vorgabe des Blocks oben links durch 9 9↑3 3⍴9?9. Allgemein gesprochen produziert TRIAL bei Vorgabe eines kompletten Blocks stets irgendwo diese "Drillinge".

TRIAL wählt die durchzutestenden Felder stets in gleicher Art und Weise aus, arbeitet die möglichen Lösungen für das gewählte Feld stets in gleicher Reihenfolge ab und beendet die Bearbeitung stets nach der ersten gefundenen Lösung. Kein Wunder, dass immer wieder die gleichen Muster auftauchen.

Beides kann einfach behoben werden.

Entweder verteile man die ersten 9 Vorgaben über alle 81 Felder:

9 9⍴((⍳81)∊9?81)\9?9

Oder man bearbeite die möglichen Lösungen einer Zelle in zufälliger Reihenfolge:

'RAN' TRIAL 9 9↑3 3⍴9?9

Der Parameter im linken Argument von TRIAL steht dabei - wie überraschend - für "random".

Mein erstes, selbst erstelltes Sudoku gehört in die Kategorie "Für blutige Anfänger". Ganz einfach zu lösen, straight forward, zu einfach.

Das liegt an der Zahl der vorgegebenen Felder: 48. Das sind zu viele.

Also was liegt näher als einige Vorbelegungen zu entfernen. Aber Vorsicht! Der Schwierigkeitsgrad muss beibehalten werden, das resultierende Sudoku soll weiterhin mit SCAN und FILL zu lösen sein.

Genau das macht meine Funktion OPT_SUDOKU, die eine gewünschte Anzahl Vorbelegungen entfernt unter Beibehaltung der gewünschten Anforderung.

Und dies ist die Variante meines ersten Sudokus, vermindert um 21 zufällig ausgewählte vorbelegte Felder:


Das sieht doch schon anspruchsvoller aus.

"Sudoku Solver by Logic" bewertet dieses Sudoku mit einem Score von 108. Schwere Sudokus haben dort einen Score von 117, mittel schwere eine von 60.

"Mein Erstes" erhält dort einen Score von 40 - "easy".

Geschrieben, getan!

Nein, ich meine nicht das erste Sudoku, das ich jemanls gelöst habe (das habe ich nicht mehr), sondern das erste, das ich erstellt habe.




Und so wurde es gemacht:

Noch einige Worte zu meinem Trial-and-Error-Funktion ...

Mit wenigen Änderungen finde ich alle möglichen Lösungen zu einem Sudoku. Anstatt bei der ersten gefundenen Lösung (siehe 3.2) aufzuhören, kann man auch alle Kandidaten bis zum bitteren Ende durchlaufen und die jeweiligen Lösungen sammeln. Je nachdem wie das Problem gestellt ist, können das sehr viele werden, so viele, dass einem der Workspace um die Ohren fliegt. Was da passieren kann, habe ich noch nicht ausprobiert, ich tippe mal irgendwo in den Tiefen der Rekursion auf einen WS Full.

Lösungen sammeln war aber nie der Anlass für den Trial-and-Error. Es war die Idee, damit einen billigen Sudoku-Generator zu bekommen. Und das funktioniert prächtig:

Erst wollte ich nie einen eigenen Sudoku-Löser schreiben, dann habe ich doch einen implementiert. Zwar nur einige logische Methoden, aber immerhin.

Dann wollte ich kein Trial-and-Error-Verfahren vorsehen, aber auch hier bin ich mir jetzt untreu geworden. Es war ja so verlockend einfach:

Versuche zuerst ein Sudoku mit logischen Methoden zu lösen, soweit es geht. Als Ergebnis erhalte ich

(1) entweder ein nicht lösbares Sudoku,
(2) ein vollständig gelöstes Sudoku
(3) oder ein Sudoku, das sich nicht weiter mit den vorhandenen logischen Methoden lösen lässt.

Bei (1) gibt es keine Lösung des Sudokus, bei (2) habe ich eine Lösung gefunden, bei (3) tue ich das, was ich nie tun wollte: ich führe den Rechner in Versuchung.