Sudoku

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.

Du bist nicht allein ...

Selbst nicht mit so abgedrehten Kombinationen wie Sudoku und APL. Ich wollte ja nie einen Vortrag über meinen computergestützten Sudokulöser (CASS, hiermit beanspruche ich das Copyright) halten. Vielleicht wird ja doch was daraus.

Normalerweise trage ich ja über ernsthafte Dinge des APL-Lebens auf meiner Lieblingsveranstaltung vor. So auch nächste Woche. Sicher, Sudoku wäre eine Alternative gewesen, aber zwei Vorträge vorbereiten war ich dieses mal nicht bereit. Auch hätte ich dann vier Slots belegt, das wäre maßlos übertrieben.

Als ich die Agenda von nächster Woche sah, war ich dann schon positiv überrascht:

11:45 - 12:30 Rätseln über Sudoku in APL2
Eine Analyse des japanischen Zahlenrätsels / Dr. Helmut Engelke
12:30 - 13:30 Mittagspause
13:30 - 14:15 Alle meine Funktionen / Axel Holzmüller

Erste Frage: Wer ist Dr.Helmut Engelke? In dieser Arbeitsgruppe ist er nicht Mitglied. Aber wozu gibt es Google ...

[PDF] ?NJ+Hmspl_j ?NJ+Hmspl_j ?NJ+Hmspl_j ?NJ+Hmspl_j
Dateiformat: PDF/Adobe Acrobat
Dr. Helmut Engelke. Musik liegt in der Luft. Analyse und Entwurf. musikalischer Stimmungen. mit APL2. 4. Mathias Kutzner. Geschlossene Gesellschaft ...
www.rhombos.de/shop/c/file/000189/APL12000.pdf

Wie konnte mir das entgehen. Ein Artikel über zwei meiner Hobbies: APL und Musik (ich ziehe allerdings andere Arten von Musik vor). Ich werde diesen Artikel lesen müssen!

Zweite Frage: Was will der Autor konkret analysieren? Aber das ist ja Thema des Vortrages. Also kann ich hier nur spekulieren.

Gemeint ist hier die APL-Funktion transponieren, das Vertauschen von Achsen einer mehrdimensionalen Struktur.

Die meisten von uns kennen Transpose angewandt auf eine 2-dimensionale Matrix: ⍉9 9⍴⍳81. Hier werden Spalten mit Zeilen vertauscht.

Das ist schon alles, was man an Achsen einer Matrix vom Rang 2 vertauschen kann. Das ist bei fünfdimensionalen Objekten anders:

1 4 5 2 3⍉SL vertauscht die Bedeutung von Zeilen und Spalten,
1 2 4 3 4⍉SL vertauscht die Bedeutung von Zeilen und Blöcke und
1 4 2 5 3⍉SL vertauscht die Bedeutung von Spalten und Blöcke

eines Sudokus in der zugehörigen Lösungsmatrix.

Es gibt noch viele weitere Möglichkeiten für das linke Argument von ⍉, sie sind aber ohne Bedeutung für die Lösung von Sudokus mit fünfdimensionalen booleschen Matrizen.

... kommt gerade zum Tragen bei der Implementierung von Sodoku-Lösungsstrategien. Ein Sudoku sieht aus wie eine Matrix und lässt sich auch so darstellen. Um solche eine Sudoku-Matrix - ob zwei- oder fünfdimensional - als Einheit zu bearbeiten, braucht ich mit APL keine einzige Schleife. Das Objekt der Begierde wird einfach nur einer Reihe von APL-Operationen unterzogen, die auf jedes Element der Matrix wirken.

Das klingt sicher erstmal sehr abstrakt. Daher werde ich hier versuchen, dies an folgenden Beispiel zu illustrieren.

Ein gelöstes Sudoku enthält in jeder Zeile, in jeder Spalte und in jedem 3x3-Block jeweils alle Zahlen von 1 bis 9. So ist die Regel. Mit APL lässt es sich nun ganz einfach überprüfen, ob eine vorgegebene 9x9-Matrix SD ein gelöstes Sudoku darstellt:

^/(⍳9)^.∊SD,(⍉SD),9 9⍴3 1 4 2⍉3 3 3 3⍴SD

Das ist so nicht ganz korrekt. Es sollte heißen: Alles oder Ein. Ich weiß, Das ist kein Deutsch!

"Alles" meint Folgendes: Natürlich habe ich alle vorhandenen Lösungsfunktionen in einer Funktion verpackt, so dass ich mit einem Funktionsaufruf ein Sudoku lösen kann - soweit ich mit den implementierten Methoden komme:

RESULT SOLVE sudoku

SOLVE führt solange iterativ FILL, SCAN, ELIM u.a. aus, bis die Lösungsmatrix sich nicht mehr verändert. Ergänze ich SOLVE noch um ein Trial-and-Error, so löst SOLVE jedes Sudoku. Das zeigt mir dann aber nur, ob ein vorgegebenes Problem überhaupt lösbar ist, also ein gültiges Sudoku. Das interessiert mich aber nicht wirklich, dazu reicht schon eine Trial-and-Error Funktion.

So zeigt SOLVE wie weit ich mit den eingebauten Methoden komme. Mit eingeschalteter Erklärungsfunktion wird mir sogar Schritt für Schritt erläutert, wie sich der Lösung genähert wird.

Apropos "Schritt für Schritt" oder "Ein":

... ein Sudoku lösen: Ohne Versuch und Irrtum, nur durch logisches Kombinieren oder Ausschließen von Lösungen. So gehen menschliche Sudoku-Löser an die Sache, solange bis es mit diesen Methoden nicht weitergeht.

Nachdem ich meine Darstellung eines Sudokus bzw. seiner möglichen Lösungen im APL festgelegt hatte, habe ich verschiedene "logische" Lösungsmethoden implementiert. Nicht alle, aber die einfachsten und wichtigsten, da mit ihnen alle leichten, mittel- und die meisten schweren Sudokus lösbar sind. Die dazugehörigen Funktionen heißen FILL, SCAN, ELIM, ELIMB und PAIR.

Jede dieser Funktionen wendet eine spezifische Methode nacheinander entlang der Zeilen, der Spalten und Blöcke an. Dafür ist jeweils nur eine Implementierung nötig. Denn die Anwendung einer Methode auf die Zeilen eines Sudokus ist das gleiche wie die Anwendung der Methode auf die Spalten des zugehörigen transponierten Sudokus. Das gleiche gilt für Zeilen und Blöcke (wegen Transitivität dann auch für Spalten und Blöcke) .

Dafür war die Darstellung einer Sudoku-Lösung als logische Matrix vom Rang 5 gedacht.

So gefällt er mir ...

... mein Sudoku-Löser. Der, den ich nie schreiben wollte.

Es ist auch ok, wenn er - Stand heute - nicht alle Sudokus lösen kann. Leichte, mittelschwere und schwere scheinen kein Problem zu sein. Bei sehr schweren erhalte ich schon mal nur einen Zwischenstand.

Aber mein Sudoku-Löser soll mir beim Lösen von Sudokus helfen. Und das tut er auch: Wenn ich nicht weiterkomme, kann ich mir Tipps für eine weiterbringende Methode holen.

Aber nicht nur das: Mein Sudoku-Löser kann mir auch "erklären" was er Zug um Zug getan hat.

Es fehlen nun noch einige weitere "logische" Eliminierungsmethoden und die finale Lösungsmethode - Trial and Error. Letztere ist auch die, die der menschliche Löser anwenden muss, wenn er mit den "logischen" Methoden nicht mehr weiterkommt.