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ß!

Auch ich habe meine "Kenner der Datenbankszene", die ich hier zu Wort kommen lasse.

Korrektur: nicht zu Wort, sondern zu Tabelle:

DB2 9 Oracle10g R2 MS SQL Server 2005 Best Good Good Best Good Worst Good Best Good Best Good Worst Good Worst Best Best Good Best Best Good Worst

Zugegeben, die erste Spalte habe ich nicht mitgenommen. Hier stehen normalerweise Kategorien mit Datenbank-Eigenschaften, die in den folgenden Spalten pro DBMS wie zu sehen bewertet wurden.

Man kann dem Autor nicht unterstellen, dass er alles nur durch die blaue Brille sieht. Ich halte ihn daher für objektiver, also vertrauenswürdiger als anderer Leute "Kenner der Datenbankszene". Außerdem:

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".

Oracle behebt mit dem aktuellen Patch alleine 23 Fehler in seiner Datenbank, 65 Bugs in allen Produkten. Die CW bezeichnet den aktuellen "Critical Patch Update" sinnigerweise als Patch-Fest.

Solche Feste kann man als Oracle DBA eigentlich nur mit viel Alkohol ertragen.

Apropos "behebt": Oracle-Kunden machen häufig die Erfahrung, dass Oracle-Patches neue Fehler produzieren. Dazu noch ein Zitat aus der erschütternden Dokumentation "Oracle hat ein Sicherheitsproblem":

"Leider schleichen sich in die Updates aber immer wieder Fehler ein, so dass sich Anwender nicht hundertprozentig darauf verlassen können, ob ein Patch funktioniert und tatsächlich alle Schwachstellen wie erwartet beseitigt."

UNIQUE ist nicht die einzige Neuerung der Version 6.2. Da gibt es noch vier weitere bemerkenswerte Dinge:

⎕MOM-Objekte enthalten jetzt ⎕FX als Methode zur Erstellung einer Funktion in einem Objekt. So wird mit

mom_obj.⎕FX cr

die Zeichenmatrix cr zu einer Funktion innerhalb des Objekts mom_obj erhoben.

)OUTPUT wurde bereits mit Version 6.0 eingeführt und erhält in Version 6.2 mit STRICT eine weitere Option. Sowohl )OUTPUT ERROR als auch )OUTPUT STRICT sind sinnvoll, um nicht gewollte implizite Ausgaben in Funktionen aufzuspüren.

)OUTPUT STRICT ist eine Verfeinerung von )OUTPUT ERROR. Bei dieser Option wird nur dann ein "IMPLICIT OUTPUT" Error ausgeworfen, wenn eine sichtbare implizite Ausgabe produziert wurde. Die Fehlermeldung erscheint nach der Ausgabe.

APL+Win hat mit der Version 6.2 eine neue Grundfunktion spendiert bekommen: UNIQUE. Damit einher geht auch die Notwendigkeit für die Belegung eines Symbols. Das ist typisch für APL. Es ist nicht gerade überraschend, dass für UNIQUE "Cup" ∪ gewählt wurde.

Syntaktisch ist ∪x äquivalent zum Unique-Idiom:

((x⍳x)=⍳⍴x)/x

Also: rechtes Argument ist ein beliebiger Vektor. Das Ergebnis ist wiederum stets ein Vektor, der alle unterschiedlichen Element des rechten Arguments enthält in der Reihenfolge ihres ersten Auftretens.

Die Implementierung von UNIQUE scheint keine Performance-Vorteile im Vergleich zum Idiom zu bringen. Der Vorteil der Nutzung liegt also alleine in der bequemeren Schreibweise.

Ich halte das für ausreichend, um ∪ statt des Idioms zu nutzen.

Sowohl UNIQUE als auch das Idiom sind vergleichsweise sehr langsam für Floating Point Argumente. Das liegt wohl daran, dass hier jeweils zur Bestimmung von Gleichheit ⎕ct herangezogen werden muss.

Kaum ist die Version 6.0 raus und verfügbar, schon gibt es ein Upgrade. Das ist gut und nicht schlecht. Denn die Version 6.2 enthält einige interessante Neuerungen und Erweiterungen.

APL+Win 6.2 ist verfügbar für Kunden mit einer APL+Win 6.0 "Subscription", das ist eine Lizenz zum Upgraden. Eine Vollversion soll demnächst angeboten werden.

Die erste Neuerung ist die UNIQUE-Grundfunktion. Für mich eine freudige Überraschung. Das ist eine sehr nützliche Spracherweiterung!

Wie die neue Grundfunktion aussieht und wie sie funktioniert lässt sich aus der Ankündigung nicht ersehen. Genauso wenig wie Details zu den weiteren neuen Features:

"The implementation of ⎕FX for ⎕MOM object system objects.

The new ")OUTPUT STRICT" state that only produces "IMPLICIT OUTPUT"
errors when visible output is generated.

The new Zip class for ⎕wi that will allow zipping and unzipping of files.

The new Session Manager printer margin settings."

Spannend und bestimmt nützlich ist auch die Unterstützung für zip.

Also werde ich auf 6.2 upgraden.

Wohl dem, der eine "Subscription" hat.

Mit der Version 6.0 unterstützt APL+Win nun auch Unicode-Daten.

Dies hatte ich in meinem Blog-Eintrag zu den Neuerungen dieser Version nicht erwähnt - aus zwei Gründen: Die Unterstützung ist noch nicht vollständig und ich hielt den Bedarf hier im Lande für nicht so gravierend. Falsch, letzteres ist falsch. Also Schade über mein Haupt. Ich gelobe Besserung.

APL2000 schrieb zur Unicode-Unterstützung

Initial Support for Unicode Character Data
⎕UCS system function supports a 32-bit Unicode character data representation. Initially support is provided for some primitives and planned for others and the other primitives yield the appropriate NONCE or DOMAIN error messages.
Unicode character data displayed in the Session Manager will be shown as <<<UCS Characters>>>.
The ⎕WI interface with Windows has been enhanced to interchange Unicode character data with ActiveX controls. The unicodebstr property has been added to control this behavior.

Auf den DPC-Seiten findet man

Unicode-Unterstützung
APL+Win V6 bietet erstmals eine Unterstützung für Unicode-Daten. Die Unterstützung von Unicode ist noch nicht in vollem Umfang implementiert und soll in späteren Releases weiter ausgebaut werden. Zunächst unterstützen nur die APL-Funktionen JOIN bzw. RAVEL (,⍪), SHAPE bzw. RESHAPE (⍴), PICK (⊃), ENCLOSE (⊂) und FIRST (↑) diesen Datentyp.
Eine neue Systemfunktion ⎕UCS dient zur Erzeugung von Textvektoren aus Unicode, ⎕DR wurde um den Datentyp 322 für Unicode-Textvektoren erweitert.

An diesem Text hatte ich noch selbst rumkorrigiert.

Mein erster Einwand bleibt richtig: Die Unterstützung ist noch nicht vollständig. Schön ist, dass APL+Win die gleiche Systemfunktion für die Konvertierung von und zu Unicode-Zeichen verwendet wie APL2.

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.