Arthur Whitneys Einzeiler-Sudoku-Solver (2011)

 (dfns.dyalog.com)
1 Punkte von GN⁺ 2024-10-07 | 1 Kommentare | Auf WhatsApp teilen
  • Dyalog APLs sudoku gibt aus einer Rätselmatrix, in der leere Felder als 0 markiert sind, alle möglichen Lösungsmatrizen zurück und implementiert dasselbe Problem im APL/K-Stil auf mehrere Arten
  • Das Standardziel ist ein 9×9-Sudoku, bei dem jede 3×3-Box, jede Zeile und jede Spalte die Zahlen 1 bis 9 ohne Wiederholung enthalten muss
  • Die Eingabe prob enthält 1–9 in ausgefüllten Feldern und 0 in leeren Feldern; mit dem optionalen linken Argument shape lassen sich auch nichtquadratische Boxen wie 2×3 oder 3×4 angeben
  • Der Lösungsalgorithmus von Veli-Matti Jantunen vektorisiert die Matrix, erstellt Indizes für Zeilen, Spalten und Boxen und erweitert dann schrittweise Kandidaten, beginnend mit der am stärksten eingeschränkten Gruppe
  • Die Beispiele s33 und s22 haben jeweils 3 Lösungen, 3 4 sudoku s34 hat 2 Lösungen; außerdem werden Arthur Whitneys K-5-Einzeiler und mehrere APL-Neuimplementierungen vorgestellt

Sudoku-Eingabe und Ergebnis der Funktion sudoku

  • Ein Sudoku-Rätsel ist ein Gitter aus 3×3-Boxen, die wiederum 3×3 angeordnet sind; jedes Feld ist entweder leer oder enthält eine Zahl von 1 bis 9
  • Eine Lösung muss alle drei Bedingungen erfüllen, die Duplikate verbieten
    • Jede 3×3-Box enthält die Zahlen 1 bis 9 ohne Wiederholung
    • Jede Zeile mit 9 Feldern enthält die Zahlen 1 bis 9 ohne Wiederholung
    • Jede Spalte mit 9 Feldern enthält die Zahlen 1 bis 9 ohne Wiederholung
  • Die Matrix prob verwendet die Zahlen 1–9 für ausgefüllte Felder und 0 für leere Felder
  • Das optionale linke Argument shape gibt die Boxform von Rätseln an, die nicht dem quadratischen Standard entsprechen
    • Wenn in einer 6×6-Matrix die Teilbereiche 2×3 groß sind, wird sie in der Form 2 3 sudoku mat aufgerufen
  • Das Ergebnis ist ein Vektor, der alle Lösungsmatrizen enthält
    • Wenn es keine Lösung gibt, wird ⍬ zurückgegeben
    • Fehlerfälle können als '' dargestellt werden; in der Dokumentation steht dazu „sollte nicht auftreten, außer wenn die Ergebniszahl enorm groß ist“

Ablauf von Veli-Matti Jantunens Lösung

  • Der Algorithmus behandelt die Sudoku-Matrix als Vektor und stellt Zeilen, Spalten und Sudoku-Regionen jeweils als Indexvektoren dar
  • Nach den grundlegenden Prüfungen werden Alternativen aus der Kandidatenliste nacheinander geprüft
  • In jedem Schritt werden die möglichen Elemente aller Felder gefiltert
    • Wenn auch nur ein Feld keinen möglichen Wert hat, wird der Lösungskandidat verworfen
    • Wenn ein Feld mehr als eine Kandidatenzahl hat, wird aus der am stärksten eingeschränkten Gruppe ein Feld ausgewählt und die Kandidatenkombinationen dieses Felds werden der Liste hinzugefügt
    • Wenn für jedes Feld nur noch genau eine Zahl übrig ist, wird dies als Lösung behandelt und mit dem nächsten Kandidaten fortgefahren
  • Derselbe Abschnitt enthält auch die Funktion Shuffle, die eine vorhandene Sudoku-Tabelle in eine andere Tabelle ummischt

Arthur Whitneys Einzeiler und alternative Implementierungen

  • David Crossleys alternative sudoku-Implementierung nimmt eine N×N-Konfiguration als Eingabe und zielt auf Fälle, in denen die Boxgröße N*÷2 eine ganze Zahl ist
    • Die Eingabe muss eine gültige Belegung sein, bei der einige Felder Zahlen von 1 bis N enthalten und die übrigen 0 sind
    • Jede Zeile, Spalte und Box muss im Ergebnis alle Zahlen von 1 bis N enthalten
    • Intern gibt es Hilfsfunktionen wie valid, search, rules, sole, singles, uniques, matches, NinN, setup
  • Arthur Whitneys K-5-Lösung wird als Einzeiler-Code gezeigt
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last stellt eine sudoku-Implementierung bereit, die Whitneys Code in eine D-function überträgt
  • Morten Krombergs Neuformulierung definiert einige Bestandteile von K explizit und bleibt damit näher am Original
    • Wie die K-Version nimmt sie keinen Matrix-, sondern einen Vektor mit 81 Elementen entgegen und gibt einen solchen zurück
  • Roger Huis Sudoku-Implementierung ist stärker verallgemeinert und verarbeitet auch nichtquadratische Rätsel
    • svec erzeugt Lösungsvektoren, pvex und pvec entfalten mögliche Belegungen
    • avl erstellt eine Liste möglicher Zahlen, und emt findet die Zeilen- und Spaltenindizes leerer Felder
    • rcb, box, cmap, CMAP konstruieren die Konfliktbeziehungen zwischen Zeilen, Spalten und Boxen

Beispielrätsel und Anzahl der Lösungen

  • s33 ist ein 9×9-Beispielproblem, und das Ergebnis von sudoku s33 hat 3 Lösungen
  • Die Funktion sbox teilt die inneren Boxen auf, um das Sudoku-Gitter leichter lesbar darzustellen
    • 0 wird als Punkt (·) angezeigt
    • Die Ausgabe erfolgt als Zeichenmatrix mit eingezeichneten Boxgrenzen
  • s22 ist ein 4×4-Beispielproblem, und das Ergebnis von sbox¨ sudoku s22 hat 3 Lösungen
  • s34 ist ein Beispielproblem mit 3×4-Boxen
    • Mit 3 4 sbox s34 wird das Problem mit Boxtrennung angezeigt
    • Das Ergebnis von 3 4 sudoku s34 hat 2 Lösungen

Referenzlinks und verwandte Einträge

  • sudoku_bfs ist als Beispiel verlinkt, das diesen Algorithmus zeigt
  • „Learn“ von TryAPL enthält eine Schritt-für-Schritt-Demo: http://www.TryAPL.org
  • Es gibt ein Video, das das Laufzeitverhalten zeigt: http://www.youtube.com/watch?v=DmT80OseAGs
  • Als verwandte Einträge werden queens, sudoku_bfs, X, sudokuX genannt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-07
Hacker-News-Kommentare

  • Diese Zeile ist in K geschrieben. K ist eine Sprache, die Arthur Whitney auf Basis von APL und Scheme entwickelt hat.
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • Manchmal schätze ich die Komplexität von Code ein, indem ich die Anzahl der Codezeilen mit der folgenden Ausgabe vergleiche:
    tar -cf - . | gzip | base64 | wc -l
    Also im Grunde: „Wie gut lässt er sich komprimieren?“ Wenn ich APL sehe, erinnert mich das an den Moment, in dem man versehentlich die gzip-Ausgabe ins Terminal geschickt hat.
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    Beeindruckend ist, dass es Leute gibt, die solchen Code durchgehen und sogar fragen: „Kannst du den Bug finden?“ Es fühlt sich an wie komprimierte Binärdaten, bei denen alle bereits dasselbe Wörterbuch besitzen.

    • Ich frage mich wirklich, wie APL-Programmierer über Wartbarkeit und Lesbarkeit denken. Kommentieren sie den Code extrem sorgfältig oder dokumentieren sie ihn separat?
    • Bei „Kannst du den Bug finden?“ sehe ich sofort ein paar Dinge. Es gibt Syntaxfehler wie ein nicht geschlossenes einfaches Anführungszeichen und ein ∘ ohne rechten Operanden; n n←⍴⍵ sieht so aus, als werde n zweimal gesetzt und als erwarte man, dass ⍵ zweidimensional ist, aber je nach Absicht wären _ n←⍴⍵ oder n←⊃⌽⍴⍵ natürlicher.
      Außerdem wirft ⊥ einen Fehler, wenn ⍴⍵ kein einzelner Integer oder leerer Vektor ist, ist am Ende also nicht wirklich anders als n←⍴⍵ und damit eher verwirrend. Mehrere redundante , und ↑⍵ lassen sich ebenfalls entfernen, und der gesamte Ausdruck wird praktisch fast zu p←(n+1)⍴⊂⍳n×n←⍴⍵: eine Struktur, die n+1 Vektoren von 1..n² ausgibt.
      Auch wenn es auf den ersten Blick seltsam wirkt: Wenn man die Symbole und Grundoperationen lernt, ist APL überraschend geradlinig. Es dauert nur, bis man darin geübt ist, und wenn man diesen Punkt erreicht, fühlt es sich wie eine Superkraft an.
    • Wenn man bedenkt, dass Milliarden Menschen Zeichen lesen und schreiben, die nicht Englisch sind, weiß ich nicht, ob es besonders oder überraschend ist, dass es Leute gibt, die APL lesen.

  • Es stimmt, dass Befürworter der Sprache Geschwindigkeit, einfache Array-Verarbeitung und eine ausdrucksstarke Syntax betonen.
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • Ob Wartbarkeit allerdings ebenfalls ein Vorteil ist, weiß ich nicht.

  • Die Anzahl der Codezeilen ist kein guter Messwert, weil jede Sprache Zeilen anders nutzt.
    Ein besseres Maß könnte sein, die Anzahl der Syntaxbaum-Knoten nach sinnvollen Nichtterminalsymbolen wie „Konstante“ oder „Funktionsaufruf“ zu zählen. Noch besser wäre es, zusätzlich die Tiefe und den Verzweigungsfaktor dieses Baums zu berücksichtigen.

    • Der Vorstellung, dass nur die Semantik zählt, kann ich nicht einfach zustimmen. Die User Experience einer Sprache, Klarheit, Denkweise und Ausdruckskraft sind ebenfalls wichtig, und die visuelle Größe des Codes beeinflusst das.
      Eine Ein-Zeilen-Lösung nimmt kaum Bildschirmfläche ein, was bei komplexen Problemen ein großer Vorteil ist. Die Augen innerhalb eines Bildschirms zu bewegen, ist deutlich weniger anstrengend, als zwischen Dateien zu wechseln und zu scrollen; kognitive Last ist wichtig.
      Selbst wenn man K nicht kennt, wirken nebeneinanderstehende Konstanten wie eine direkte Datenrepräsentation des Problems. Wenn die K-Kultur solchen Code fördert und das Denken in Richtung Direktheit und Einfachheit verschiebt, würde ich diese Spezialsauce gern ins Team holen.
    • Built-in-Funktionen und Systembibliotheks-APIs machen solche Metriken kaputt. HQ9+ ist zum Beispiel ziemlich gut darin, „Hello, world!“ auszugeben.
      https://cliffle.com/esoterica/hq9plus/
    • Das bevorzugte Maß für Informationsgehalt ist, wie in der algorithmischen Informationstheorie, schlicht die Anzahl der Bits.
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Dieser Einzeiler ist eindeutig zum Spaß gemacht, und niemand behauptet ernsthaft, dass er gut lesbar sei. Sich hier an Definitionen aufzuhängen, verfehlt den Punkt. Die Aussage ist: „In K kann man extrem dichten Code schreiben.“

  • Ich habe mich oft gefragt, ob Sprachen wie APL/K Programmierern tatsächlich helfen, Probleme effizienter zu durchdenken.

    • Als kdb+/Q-Programmierer würde ich sagen: Es hängt von der Problemart ab. Beim Arbeiten mit Daten-Arrays ist es definitiv einfacher, das Addieren zweier Arrays und anschließende Mitteln als avg a+b zu denken und zu schreiben.
      In einer nicht arrayzentrierten Sprache bräuchte man wahrscheinlich Bounds-Checks, eine große for-Schleife und temporäre Variablen für Summe und Anzahl. Was in einer Sprache wie C ungefähr sechs Zeilen wären, erledigt Q in sechs Zeichen.
      Allerdings hat jede Sprache Features, die das Nachdenken über bestimmte Probleme erleichtern. Funktionale Sprachen mit algebraischen Datentypen und Pattern Matching, etwa OCaml oder F#, sind besser als ein großer switch oder if-else-if, und Sprachen mit syntaktischem Zucker wie async/await sind bei Nebenläufigkeit im Vorteil.
    • Bei Problemklassen, die sich leicht vektorisieren lassen, machen arrayzentrierte Sprachen Denken und Lösungen effizienter, weil sie Details von Datenstrukturen und Iteration abstrahieren.
      Als Quant habe ich über fünf Jahre lang viel kdb+/q für Strategien mittlerer Frequenz genutzt. Als ich aber in den Hochfrequenzhandel wechselte, wo Dinge wie Orderbuch-Berechnungen nicht leicht oder effizient vektorisierbar sind, machte die weitere Nutzung einer arrayzentrierten Sprache das Nachdenken über die Probleme eher komplizierter.
    • In einem Vortrag über Dyalog, eine moderne Sprache aus der APL-Familie, hörte ich die These, dass diese Notation bestimmte Idiome leichter erkennbar macht.
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      Der betreffende Abschnitt stand im Compiler-Kontext, aber der gesamte Vortrag behandelt Dyalog und APL als mathematische Notationssysteme. Der Kern ist, dass es leichter sein kann, mathematische Ausdrücke zu optimieren als gewöhnlichen Code.
    • Hillel Wayne behandelt dieses Thema gelegentlich in seinem Newsletter. Ich bin überzeugt, dass er manche Probleme tatsächlich in Array-Sprachen besser durchdenken kann, aber wie sich diese Erfahrung anfühlt, kann ich mir noch nicht recht vorstellen.
    • Das Gute am Stil von Array-Sprachen ist, dass beim Diskutieren von Algorithmusvarianten die relevanten Codefragmente nur wenige Zeichen lang sind und direkt in den Fließtext passen. In traditionellen vertikalen Sprachen, die für dasselbe mehrere oder Dutzende Zeilen brauchen, muss man ständig Codeblöcke und erklärenden Text mischen.

  • Einer der wichtigsten Punkte hier ist, dass der Problemgenerator oben sehr klar ist. Das ist der Unterschied zwischen iversonschen Notationssprachen, einschließlich J und K, und anderen Sprachen.
    Er hat nicht die Eleganz und Kraft der Ein-Zeilen-Lösung, ist aber auch ohne strenge Kommentare sehr sauber und verständlich. Allerdings finde ich nicht, dass lamp ein gutes Kommentarzeichen ist.
    Die Ein-Zeilen-Lösung ist erstaunlich, und implizites Programmieren ist mind-bending cool. Die Idee, die einzigartige Komprimierbarkeit glyphenbasierter Sprachen zu nutzen, um funktionale Programmierung zu beschreiben und auszuführen, und das dann wieder auf ganze Arrays anzuwenden, ist genial.
    https://www.jsoftware.com/papers/fork.htm

    • Nur weil man alles ohne Leerzeichen in eine Zeile schreiben kann, heißt das nicht, dass man es auch tun sollte.
      Natürlich kann man, wenn man diese Fähigkeit entfernt, ausführlicheren Code erzwingen, aber dann verringert man den Wert als interaktives Werkzeug erheblich. Iversonsche Sprachen sind nützlich für interaktives Arbeiten, weil man sehr kurzen Code schreiben kann. Dieser Code wird dann nicht einmal gespeichert, ist also wirklich Write-only-Code.
      Wenn man Code schreibt, der in eine Datei kommt, kann man den gewünschten Stil wählen; dann würde ich empfehlen, weniger komprimiert zu schreiben. Trotzdem liefern iversonsche Sprachen selbst in einem ausführlichen Stil deutlich kürzeren Code als die meisten anderen Sprachen.

  • Die meisten schrecken wegen der Symbole zurück, aber mein Problem war das nicht.
    Ich mag APL und Array-Sprachen, und das, was ich gelernt habe, hat mir auch beim Einsatz anderer Sprachen sehr geholfen. Aber sie wurden nicht zu meinem Alltagswerkzeug; nicht wegen der Symbole, sondern weil ich nach etwa 3 bis 4 Jahren gelegentlicher Beschäftigung auf eine Wand stieß, über die ich nicht hinwegkam.
    In anderen Sprachen gibt es meist eine allgemeine Herangehensweise, mit der man ein Problem zumindest grob lösen kann, und später, wenn man den „Trick“ für dieses Problem findet, kann man es eleganter und effizienter überarbeiten. Bei APL fühlte es sich so an, als gäbe es keinen solchen provisorischen Umweg: Entweder man kennt den Trick oder man kennt ihn nicht.
    Ich weiß nicht genau, ob das tatsächlich so ist, ob man eine Intuition fürs Problemlösen entwickelt, wenn man genügend Tricks lernt, ob es bis zum Ende nur aus Tricks besteht oder ob ich einfach die zentralen Strategiedokumente nicht gelesen habe.

    • Dieses Gefühl ist nicht falsch. Beim Lernen von Array-Sprachen bekommt man sehr leicht diesen Eindruck. Wer sie lange verwendet, sieht ein Problem und sagt schnell: „Warum so kompliziert lösen, man kann doch einfach ⍸⍣¯1 verwenden?“ — dabei hat einem wahrscheinlich nie jemand gesagt, dass ⍸ eine inverse Operation hat und wie man sie benutzt.
      Auch heute, nach Jahren mit solchen Sprachen, finde ich manche Code-Wände, die einige Array-Programmierer erzeugen, etwas einschüchternd. Ich verstehe, warum sie so schreiben, aber persönlich bevorzuge ich Code mit etwas Leerraum.
      Ich entwickle eine APL-basierte Array-Sprache, und eines der frühen Ziele war, den imperativen Stil zu einem First-Class Citizen zu machen, ohne Anfänger zu bestrafen, die Dinge wie if-Anweisungen verwenden. Ich sehe diesen Stil ungefähr in der Mitte zwischen reinem APL-Stil und gewöhnlichen imperativen Sprachen.
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • Die erwähnte Wand ist ein echtes Problem der heutigen Einstiegswege in APL. Ich habe letztes Jahr genau über dieses Thema einen Vortrag gehalten, und es ist keinesfalls persönliche Schuld.
      Es ist aber auch keine Grenze der Sprache selbst. Meiner Erfahrung nach war der Prozess, diese Wand zu durchbrechen, genau der Prozess, in dem das Paradigma einrastete. Erst nachdem ich ein Jahr lang etwa 500 Stunden an einem YAML-Parser-Prototyp gehackt hatte, begannen die Teile zusammenzupassen.
      Der Kern scheint eine Kombination daraus zu sein, sich an datengetriebene Designprinzipien zu gewöhnen, die iversonschen Eigenschaften guter Notation konkret in der Softwarearchitektur zu nutzen, sowie Idiome und die Art, wie sie Domänenkonzepte ausdrücken, zu verinnerlichen.
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Zu diesem Thema gibt es ein Video.
    https://www.youtube.com/watch?v=DmT80OseAGs
    Die Lösung kann man direkt auf https://tryapl.org/ ausprobieren.

  • Es könnte interessant sein, diese eine Zeile mit Code-Golf-Lösungen in verschiedenen Programmiersprachen zu vergleichen.
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • Interessanterweise ist die erstplatzierte Lösung für ein bestimmtes Problem, nämlich das Brute-Force-Lösen von Sudoku, genau ein K-Snippet. Auf Platz zwei liegt eine J-Lösung, die der K-Lösung nachempfunden ist.
      https://codegolf.stackexchange.com/a/5030