Arthur Whitneys One-Liner-Sudoku-Löser (2011)

Algorithmus zum Lösen von Sudoku-Problemen

• Beschreibung des Sudoku-Problems

  • Ein Sudoku-Puzzle besteht aus 3×3-Blöcken in einem 3×3-Raster, und jede Zelle ist entweder leer oder enthält eine Zahl von 1 bis 9.
  • Jeder 3×3-Block sowie die 9 Zeilen und 9 Spalten müssen die Zahlen 1 bis 9 ohne Duplikate enthalten.
  • Es werden ein Beispielproblem und ein Lösungsweg bereitgestellt.

• Überblick über den Algorithmus

  • Die Matrix wird als Vektor verarbeitet, wobei Zeilen, Spalten und Sudoku-Bereiche als Indexvektoren dargestellt werden.
  • Eine Grundprüfung des Puzzles wird durchgeführt, und durch Filtern möglicher Elemente wird eine Lösung gefunden.
  • Wenn eine Zelle leer ist, wird zur nächsten Liste übergegangen; wenn eine Zelle mehrere Zahlen enthält, wird aus der engsten Gruppe ausgewählt und zur Liste hinzugefügt.
  • Wenn alle Zellen genau eine Zahl enthalten, wurde eine Lösung gefunden.

• Technische Notizen

  • Eine von Veli-Matti Jantunen bereitgestellte Lösung, bei der ⍺ verwendet werden kann, um das Sudoku-Rechteck darzustellen.
  • Das Ergebnis ist ein Vektor aller Lösungen, andernfalls ⍬, und bei einem Fehler wird '' zurückgegeben.
  • Der Algorithmus ist einfach: Er verarbeitet die Matrix als Vektor und findet durch Filtern möglicher Elemente die Lösung.

• Andere Ansätze

  • Es werden alternative Implementierungen von David Crossley und Arthur Whitney vorgestellt.
  • Verschiedene Codierungsstile und Ansätze werden erläutert.

• Beispiele und Einsatzmöglichkeiten

  • Es werden verschiedene Beispiele zum Lösen von Sudoku-Problemen gezeigt.
  • Außerdem wird eine Funktion bereitgestellt, die innere Blöcke trennt, damit Sudoku-Probleme leichter lesbar sind.

Zusammenfassung von GN⁺

• Es werden verschiedene Algorithmen und Codierungsstile zum Lösen von Sudoku-Problemen vorgestellt.
• Sudoku-Puzzles sind nützlich, um logisches Denken und Problemlösungsfähigkeiten zu verbessern.
• Verschiedene Ansätze können die Flexibilität beim Problemlösen erhöhen.
• Als Puzzles mit ähnlichen Eigenschaften werden Kakuro, KenKen usw. empfohlen.

[GN⁺]

Hacker-News-Kommentare

• Die Sprache K wurde von Arthur Whitney auf Basis von APL und Scheme entwickelt; hervorgehoben werden Geschwindigkeit, Array-Verarbeitung und eine ausdrucksstarke Syntax.
• Bei der Messung der Code-Komplexität werden Zeilenzahl und Verdichtungsgrad des Codes verglichen.
  • APL-Code fühlt sich wie komprimierte Binärdaten an, und ich bin beeindruckt von den Menschen, die ihn verstehen können.
• Die Anzahl der Codezeilen wird je nach Sprache unterschiedlich genutzt und ist daher kein guter Maßstab.
  • Eine bessere Messmethode wäre, die Anzahl und Tiefe der Knoten im Syntaxbaum sowie die Verzweigungsfaktoren zu berücksichtigen.
• Die Klarheit des Problems ist wichtig, und iversonsche Sprachen (einschließlich J und K) unterscheiden sich von anderen Sprachen.
  • Eine Ein-Zeilen-Lösung ist erstaunlich und nützlich, um Arrays effizient zu beschreiben und zu verarbeiten.
• Es gibt die Meinung, dass K-Programme mit QED enden sollten, und es wird über einen Zusammenhang mit KQED spekuliert.
  • KQED ist der PBS-Partner in der Bay Area.
• Es wird gefragt, ob Sprachen wie APL/k helfen, Probleme effizienter zu durchdenken.
• Das Lernen von APL und Array-Sprachen hat auch bei anderen Sprachen geholfen, sie werden jedoch nicht mehr im Alltag verwendet.
  • In APL sind Probleme schwer zu lösen, wenn man die spezifische Herangehensweise zur Lösung nicht kennt.
• Es gibt bessere Lösungen als einige ineffiziente Ansätze, die in einem Algorithm Design Handbook zu sehen waren.
  • 2015 wurde dazu ein Blogbeitrag geschrieben.
• Eine Sudoku-Lösung mit Scryer Prolog ist gut lesbar und leistungsfähig und bietet starke Constraint-Solving-Funktionen.
  • Scryer Prolog ist ein modernes, leistungsstarkes und ISO-konformes Prolog.