Welche Routinen benötigt man für einen Sudoku-Solver? (Sudoku-Solver Teil 5)

Die Antwort auf diese Frage unterteilt das Programm letztlich in zwei Bereiche: in I/O-Routinen und die Lösungsroutinen. Im Folgenden eine kurze Auflistung der erforderlichen Lösungsprozeduren:

  1. Setzen eines Wertes inkl. Sperre dieses Wertes auf Spalte/Zeile/Block des Wertes
  2. Suche nach letzter freier Stelle in einer Zeile
  3. Suche nach letzter freier Stelle in einer Spalte
  4. Suche nach letzter freier Stelle in einem Block
  5. Suche nach letzter Position für einen Kandidaten in einer Zeile
  6. Suche nach letzter Position für einen Kandidaten in einer Spalte
  7. Suche nach letzter Position für einen Kandidaten in einem Block
  8. Paarsuche
  9. Doppelpaarsuche
  10. Autosolver; Schleife, welche die anderen Routinen aufruft

Die Algorithmen für 2/5, 3/6 und 4/7 lassen sich sinnvoll in je einer Routine zusammenfassen, was Schleifendurchläufe spart. Ergänzend kann man auch 2/3/5/6 komplett zusammenfassen. Das fördert zwar nicht die Lesbarkeit des Quellcodes, verringert aber nochmals die notwendigen Prozeduren und auch Schleifendurchläufe. Die Realisierung innerhalb meines Sudoku-Solvers in v0.4 hat dieses Konzept so umgesetzt, dürfte aber noch weiter optimierbar sein. Noch nicht vollständig implementiert ist die Paarsuche – die Nachbesserung sollte dann später in v0.5 enthalten sein.

Für den I/O-Bereich sind folgende Routinen relevant:

  1. Einlesen der Rätsel aus Textdateien
  2. Speichern von Lösungen
  3. Anzeige des (Zwischen-)Ergebnisses
  4. Möglichkeit der Ausgabe von Debug-Infos, Löschen der zugehörigen Liste etc.
  5. Ausgabe von übrigen Kandidaten

Letztere Option kann dazu dienen, Rätslern Unterstützung bei bestimmten Aufgaben zu liefern, dient nebenbei auch der Fehlersuche bei der Optimierung von Algorithmen bzw. der Entwicklung neuer Algorithmen.

Im Sudoku-Solver sind die Debug-Infos im Quelltext auskommentiert; wer diese haben möchte, muss einfach nur Lazarus installieren, ein paar Kommentarzeichen (Debug-Infos beginnend mit if ChkBox_Verbose.Checked then) entfernen und neu kompilieren. Theoretisch sollte das Tool Dank Lazarus auf diversen Plattformen lauffähig sein. Bei einem Test unter Linux zeigte sich allerdings, dass dort irgendetwas beim Einlesen der Textdateien nicht klappt – da müsste also noch nachgebessert werden.

Um besser nachvollziehen zu können, welcher Algorithmus was bewirkt, kann man die Routinen des Tools einzeln aufrufen. Allerdings ist die Aktualisierung der Anzeige für Einzelschritte auskommentiert, müsste also bei Bedarf auch noch schnell im Quelltext (Aufruf von ShowArray) angepasst werden.

Als Grundlage für die Speicherung der Rätsel-Daten verwendet das Tool ein 25×25-Array, welches einen selbst definierten Datentypen (record, analog zum struct in C/C++) nutzt. In den ersten Versionen des Tools hatte ich hierbei die Kandidaten als Integer gespeichert, was aber bei der Verarbeitung der logischen Operationen innerhalb der Doppelpaarsuche und der (noch nicht implementierten) Paarsuche kaum noch zu überblicken ist. Deshalb bekam schon die (nicht veröffentlichte) Version v0.3 eine neue Datenstruktur aufgedrückt. Die Kandidaten werden nunmehr binär in einem uint64 (unsigned Integer mit 64 Bit) gespeichert, wodurch binäre Filter über die Kandidatenlisten verwendbar sind. Logische Operationen können dadurch mit hochperformanten boolschen Operationen ausgeführt werden. Schon zu 486er Zeiten waren für AND/OR/XOR/NOT über Variablen in Busbreite nur 1-3 Takte pro Befehl (abhängig davon, ob die Variablen in Registern, im Speicher oder als Zahlenwert vorliegen) erforderlich.

Zwar konnte ich mit meinem Lazarus-Standardpaket keinen 64-Bit-Code erstellen, dies wird aber mit Sicherheit irgendwann möglich sein, so dass mein Sudoku-Solver dann auf entsprechenden Systemen automatisch deutlich schneller arbeiten würde.

Der Sudoku-Solver v0.4 kann fast alle rein logisch lösbaren Sudokus mit 3×3-, 4×4- und 5×5-Matrix lösen. Für Rätsel, die nur durch weitere Algorithmen oder eine ergänzende Backtracking-Methode gelöst werden können, bietet das Tool einen guten Einstieg, da die verbleibenden Kandidaten der freien Stellen angezeigt werden können.
Eine Erweiterung auf Unterstützung von 6×6 und 7×7 wäre durch C&P weniger Quelltextzeilen (procedure TForm1.MenuDateiLadenClick) und Änderung einiger Zahlen (const maxVal und die Lade-Prozedur) möglich. Eventuell würde sogar 8×8 gehen. Dabei bin ich mir allerdings nicht ganz sicher, da dies zu Unstimmigkeiten im verwendeten Datentypen (uint64) führen könnte. Auf jeden Fall würde eine solche Erweiterung bedeuten, dass man sich auch noch etwas praktikables für die Anzeige des Rätsels bei kleinen Bildschirmauflösungen einfallen lassen müsste.

Download: Sudoku-Solver, aktuell in v0.6.1 <- Update 15.02.2010
Hinweis: Lazarus baut ziemlich große ausführbare Dateien, schon ein leeres Windows-Projekt ist 12 MB groß, die kompilierte Win-Version liegt damit um die 13 MB und die Elf-Datei für Linux bei etwa 20 MB.

4 Reaktionen zu “Welche Routinen benötigt man für einen Sudoku-Solver? (Sudoku-Solver Teil 5)”

  1. admin

    Zugehörige Artikel:
    Was ist ein Sudoku? - Teil 1
    Sudoku-Varianten - Teil 2
    Sudoku-Strategien - Teil 3
    Sudoku-Löser-Programmierung - Teil 4
    Welche Routinen benötigt man für einen Sudoku-Solver? - Teil 5

  2. admin

    Mit Freude gebe ich die Veröffentlichung des Sudoku-Solvers v0.5 bekannt.

    Liste der Änderungen:

    • Implementierung eines Algorithmus für die Paarsuche (PairSearch); nutzt die Strategien Naked Pair und Naked Triple, letztere nicht ganz vollständig (siehe Sourcecode)
    • weitgehende Beseitigung der Schleifen in der SetValue-Routine; stattdessen werden die Kandidatenlisten des zugehörigen Blocks, der Zeile und der Spalte direkt gesetzt; dadurch etwa 4-6% höhere Ausführungsgeschwindigkeit
    • zusammenfassende Kandidatenlisten für Blöcke, Zeilen, Spalten -> weitere Optimierungsmöglichkeiten; beim Setzen von Werten werden zusätzlich diese Kandidatenlisten angepasst
    • Einführung eines Zählers für die bisher gesetzten Werte; Beschleunigung der AutoSolve-Routine

    Hintergrund dieser recht umfangreichen Änderungen war neben dem allgemeinen Optimierungswunsch vor allem die Tatsache, dass ich mehrere Anläufe zur Entwicklung eines funktionierenden Paar-Suche-Algorithmus brauchte. Die ersten Versuche hatten alle irgendwelche Fehler und waren zu undurchsichtig. Der jetzt implementierte Algorithmus mag vielleicht nicht der allerschnellste sein, aber er funktioniert fehlerfrei und ist nachvollziehbar ;) Genau dafür benötigte ich allerdings auch die Zusammenfassung der in einem Block noch verfügbaren Kandidaten. Die hierfür eingeführten neuen 3 globalen Arrays könnten in späteren Versionen auch zu Optimierungen in anderen Routinen (z.B. RowColClick) dienen. Auch die BlockSearch-Routine könnte noch mal überarbeitet werden, da ein Teil davon auch in der PairSearch-Procedure enthalten ist.

    Im direkten Vergleich der v0.4 mit v0.5 für das mitgelieferte Beispielrätsel sudoku1.txt verringert sich die durchschnittliche Lösungsgeschwindigkeit (reine Lösung, die Anzeige dauert wesentlich länger) auf meinem Entwicklungssystem von ca. 140µs auf ca. 112,5µs - das sind also etwa 20% weniger Rechenzeit!
    Auch für die anderen Rätsel gibt es einen ordentlichen Performanceschub. Das Rätselbeispiel pentadoku2.txt benötigte in der v0.4 durchschnittlich 2883,3µs und braucht in v0.5 im Schnitt nur noch 2422,7µs. Es wird also knapp 16% weniger Zeit für die Berechnung benötigt.

  3. admin

    Die Weiterentwicklung geht in die nächste Runde, Version v0.6 ist fertig.

    Liste der Änderungen:

    • Optimierung der Blockverarbeitung: Integration der BlockSearch-Routinen in die Funktion der Paarsuche und weitgehende Optimierung des Codes; das Ergebnis findet sich in der neuen procedure TForm1.btn_BlockClick und bearbeitet die Strategien Block-Line-Interaction, Line-Block-Interaction, Naked Single und Hidden Single
    • neue Routine zum Test von Zeilen/Spalten; das wesentlich schnellere Ergebnis ist der gleichnamige Ersatz der alten procedure TForm1.btn_RowColClick und nutzt die Strategien Naked Single und Hidden Single
    • Anpassung des Autosolvers an die neuen Routinen und weitergehende Geschwindigkeitsoptimierung durch Verbesserung der Auswahl der ausgeführten Routinen
    • Integration eines Backtrackers, welcher die Logikroutinen mitnutzt

    In den letzten 2 Wochen sind wieder einige Zeilen Code hinzugekommen und wie in obiger Liste zu erkennen, sind vor allem auch einige Routinen komplett neu geschrieben worden. Das Ergebnis ist eine enorme Beschleunigung der Lösungsgeschwindigkeit für alle bisher unterstützten Sudoku-Rätsel-Typen.
    Da das mitgelieferte Beispielrätsel sudoku3.txt bisher vom Tool nicht gelöst werden konnte und ich beim besten Willen auch keine (überschaubare) Logik zur Eliminierung weiterer Kandidaten entdecken konnte, entschied ich mich, doch noch einen kleinen BackTracking-Algorithmus einzubauen. Die erste Variante war nicht rekursiv und konnte nur Rätsel lösen, in denen es genügte, an exakt einer Stelle den richtigen Kandidaten zu wählen. Damit konnte zwar das Beispiel gelöst werden, das Rätsel sudoku4.txt war aber noch immer nicht lösbar. Nachdem ich nunmehr bereits einen Backtracking-Ansatz implementiert hatte, war es auch nicht mehr schwierig, diesen durch eine Rekursion zu ergänzen. Im ersten Schritt versucht der jetzt in v0.6 implementierte BackTracker das Rätsel mit nur einem gewählten Kandidaten mittels der Logikroutinen zu lösen - klappt dies nicht, so wird im zweiten Schritt die Rekursion eingeleitet. In der Rekursion wird ebenfalls immer zuerst probiert, mit nur einem gewählten Kandidaten zu einer Lösung zu kommen und erst wenn dies nicht klappt, geht es eine Rekursionebene tiefer. Dadurch arbeitet auch der Backtracker extrem schnell und trotzdem gibt es mit Sicherheit noch einiges an weiterem Optimierungspotential. Ich habe dafür allerdings bisher keine Zeitmessung eingebaut, vielleicht feile ich da später noch mal dran herum … Das BackTracking liefert nur eine Lösung; wer alle möglichen Lösungen haben möchte, müsste den Code geringfügig umschreiben - die relevante Stelle ist kommentiert. Kleines Gimmick am Rande: beim Start des Sudoku-Solvers wird ein leeres 9×9-Rätsel initialisiert. Lässt man dieses per BackTracking lösen, so erhält man eine Standardlösung, die oft zum Generieren von neuen Rätseln verwendet wird.

    Kommen wir zu den neuen Messwerten in der Ausführungsgeschwindigkeit. Gewertet habe ich den Durchschnitt von diesmal jeweils nur 5-6 Durchläufen, wobei ich starke Ausreißer (manchmal beim ersten Aufruf der Funktionen oder sonstwie systembedingt) unberücksichtigt gelassen habe. Hier eine kleine Tabelle:

    Sudoku-Solver Lösungsgeschwindigkeit
    Rätsel v0.4 v0.5 v0.6
    sudoku1.txt 140.7µs 113.1µs 42.7µs
    sudoku2.txt 211.0µs 186.9µs 59.4µs
    sudoku17-0001.txt 220.0µs 189.6µs 62.0µs
    sudoku17-0003.txt 297.5µs 265.4µs 68.0µs
    sudoku17-0005.txt n.l. 345.8µs 129.6µs
    tetradoku1.txt 538.2µs 416.6µs 117.4µs
    tetradoku2.txt 398.7µs 279.4µs 82.5µs
    pentadoku1.txt 1616.4µs 1219.4µs 140.0µs
    pentadoku2.txt 2802.6µs 2453.8µs 591.0µs

    Gemessen wurde die reine Rechenzeit des auf Win-32 mit Lazarus 0.9.28-2 kompilierten Tools nach(!) dem Einlesen der Vorgaben und ohne jegliche Ausgaben mit Hilfe des EpicTimer (GPL) auf einem AMD Phenom2 X3 720 @ 3.3 GHz mit Win7-64.

    Der Performanceschub ist weitaus größer, als ich erwartet hatte. Vermutlich könnte man durch eine Optimierung auf die gängigen 9×9-Sudokus selbst für ungünstige Vorgaben mit einem reinen Logiklöser auf durchschnittliche Rechenzeiten von unterhalb 40µs mit Pascal kommen. Bei Verwendung von Assemblerroutinen sind 20-30µs denkbar. Ein eventuell lohnenswerter Optimierungsansatz wäre auch noch, die bisherigen Kandidatenarrays für Blöcke, Spalten und Zeilen durch weitere Sublisten für Zeilen/Spalten in den einzelnen Blöcken zu ergänzen. Auch die Doppelpaar-/Dreier-Suche (Naked Pair/Tripple) könnte noch weiter optimiert oder sogar in die anderen Routinen integriert werden, was vor allem für komplizierte Rätsel (z.B. sudoku17-0005.txt) einen Geschwindigkeitsschub bringen dürfte.

  4. admin

    Es gibt wieder eine neue Version v0.6.1, dieses Mal allerdings nur mit marginalen Änderungen:

    • Oberfläche optisch überarbeitet und somit übersichtlicher
    • Anpassung der Routinen zum Einlesen und Speichern von Rätseln, so dass dies jetzt auch unter Linux funktioniert
    • Vorkompilierte Versionen für Windows jetzt in 64 Bit und mit Snapshots aus den Betazweigen von Lazarus/FPC erstellt, dadurch verbesserte Performance

    Die Oberfläche war bisher offensichtlich nur eine zu Entwicklungszwecken zusammengeklickte Lösung, die nunmehr aufgeräumter daherkommt. Wer das Projekt unter Linux kompilieren will, muss dort allerdings noch mal nachbessern, da unter Linux meist andere Schriftarten verwendet werden und einige Abstände dadurch nicht stimmen. Dies ändert am eigentlichen Sourcecode nichts, nur die Projekteigenschaften müssen für Linux und Windows getrennt gespeichert werden. Auch zwischen den verschiedenen Compilerversionen gibt es Unterschiede in der project1.lpi, weshalb der aktuelle Quelltext nicht auf Anhieb in der zuvor verwendeten Lazarus-Version 2.2.4 kompiliert werden kann. Als lästig erwies sich, dass man offenbar trotz Cross-Plattformunterstützung nicht für andere Plattformen kompilieren kann, ohne dafür Lazarus neu kompilieren zu müssen. Da dies bei mir wegen undurchsichtiger Abhängigkeitsprobleme nicht funktioniert und ich nicht für Win32/64 und Lin32/64 jedes Mal die IDE+FPC neu installieren möchte, gibt es vorerst nur noch die Win64- sowie die Lin32-Variante zum Download.
    Durch die Verwendung des neueren FreePascal-Compilers unter Windows ergibt sich hier erneut eine kleine Geschwindigkeitssteigerung. Während die Umstellung auf 64 Bit nur für größere Rätsel (25×25) einen deutlich messbaren Vorteil brachte, ist die Ausführungsgeschwindigkeit des Kompilats mit dem aktuellen Beta-FPC auch schon für die 9×9-Sudokus einige Prozent besser.

    Die einzige wirkliche Änderung im Programmcode betrifft die I/O-Routinen. Während man unter Windows mittels assignfile(f,OpenDialog1.Files[0]); auf den ersten ausgewählten Dateinamen eines OpenDialog-Objekts zugreifen kann, funktioniert dies unter Linux nicht. Auf beiden Plattformen lauffähig ist hingegen die Eigenschaft OpenDialog1.FileName. Im Zuge dieser Anpassung wurde für die Read-Routine außerdem das Einlesen von Low-Level-Funktionen auf die TStringList umgestellt. Standardmäßig erfolgt der Einsatz dieser Routine wie folgt:

    if OpenDialog1.Execute then begin
       f:=TStringList.Create;
       f.LoadFromFile(OpenDialog1.FileName);
       // hier Verarbeitung der auf f liegenden Stringlist
       f.Free;
    end;
    

    Da ich nunmehr auch unter Linux testen konnte, hier noch eine kleine Vergleichsangabe: ein Atom N270 (1.6GHz; nur i386, CPU bietet keine AMD64-Unterstützung) braucht für alle Rätseltypen etwa 3.5x so viel Rechenzeit wie der oben erwähnte Testrechner mit übertaktetem Phenom2 720BE.

Einen Kommentar schreiben