Sudoku-Solver v0.7

Die Weiterentwicklung des Anfang des Jahres (siehe Routinen für einen Sudoku-Löser) begonnenen Sudoku-Solvers hat einen neuen Meilenstein erreicht. Neben optischen Änderungen sind einige Anpassungen in der Funktionsstruktur des Quelltextes und der Verarbeitung ganzer Sudoku-Listen erfolgt und ein erster (allerdings noch nicht richtig stabiler) Sudoku-Generator hat den Weg in die neue Version gefunden.

Liste der Änderungen:

  • Oberfläche übersichtlicher gestaltet, vor allem auch in Bezug auf neue Funktionalitäten; Logiklöser und Backtracker wurden verschmolzen, wobei der Backtracker per CheckBox zugeschaltet werden kann
  • Lösungsgeschwindigkeit wird jetzt auch für Backtracking angezeigt
  • Unterstützung von X-Sudokus; X-Sudokus sind Rätsel, bei denen zusätzlich für die Diagonalen gilt, dass dort jeder mögliche Wert nur genau 1x vorkommen darf; Unterstützung für alle nutzbaren Rätselgrößen (9×9, 16×16, 25×25); X-Rätsel können derzeit nur über Sudokulisten geladen werden
  • Erkennung für ungültige Sudokus; wenn eine Vorgabe ein nicht lösbares Rätsel ergibt, streng genommen also gar kein Sudoku ist, dann wird das Rätsel im Backtracker nicht weiter bearbeitet und somit die Ausführungsgeschwindigkeit enorm beschleunigt
  • Unterstützung von Sudoku-Listen; neben dem alten Dateiformat für Rätsel wurde eine neue Möglichkeit implementiert, um auch ganze Listen in einem Rutsch einlesen zu können; die Auswahl erfolgt über ein SpinEdit-Feld
  • komplette Listen in einem Rutsch lösen - wahlweise logisch oder per backtracking; es erfolgt keine Anzeige der Zwischenergebnisse, nur das letzte Rätsel und die benötigte Rechenzeit werden ausgegeben
  • automatisches Speichern der Lösungen von Sudoku-Listen (vorgegebener Dateiname wird um Endung .lsg ergänzt)
  • Sudoku-Generator; über das Extras-Menü können Sudokus generiert werden; die Funktion ist noch instabil, funktioniert für Sudokus relativ gut, für Tetradokus mittelmäßig und ist für Pentadokus bisher unbrauchbar

Vorerst stehen nur vorkompilierte Versionen für Win32 und Win64 zur Verfügung, Linux-Versionen reiche ich nach.

Hintergründe und Pläne für folgende Versionen ergänze ich hier demnächst …

2 Reaktionen zu “Sudoku-Solver v0.7”

  1. Horst

    Hallo,

    ich habe den Solver mit dem Easter Monster Sudoku gefüttert, der wohl noch mit Logik gelöst werden kann, die in Deinem solver noch nicht in allen Varianten implementiert ist.

  2. admin

    Hallo Horst,

    es gibt noch zahlreiche Logiken, die ich nicht implementiert habe. Viele davon sind auch recht kompliziert zu programmieren, z.B. die Kettenlogiken mit ihren Ausschlussverfahren. Die größte Schwierigkeit dabei ist, dass die meisten der komplizierteren Logiken jeweils nur sehr selten bei der Lösung eines Sudokus helfen und man vorher nicht weiß, ob der Algorithmus weiterhilft oder nicht. Das Ergebnis ist, dass bei Anwendung eines für das jeweilige Rätsel unbrauchbaren Algorithmus man die Lösungsgeschwindigkeit deutlich verringert und so auch im Gesamtschnitt über hunderte oder tausende Rätsel schlechter fährt, als wenn man nur eher einfache Logiken und anschließend einen Backtracker ansetzt.
    Im April/Mai letzten Jahres hatte ich für meinen Sudoku-Solver einige wesentlich komplexere Lösungsalgorithmen entwickelt und auch alle vorhandenen ersetzt. Mangels Zeit konnte ich das Projekt nicht zu Ende führen, es zeigte sich aber, dass durch den höheren Overhead der größeren Anzahl von Zwischenergebnissen (Speicherung aller Zeilen/Spalten binär auch auf Blockbasis, also in einer 3er-Basis -> Optimierung zu Gunsten umfangreicherer binärer Filter) der Gesamtschnitt der Lösungszeiten etwas schlechter war - eine Weiterentwicklung könnte dies u.U. beheben, vielleicht aber auch nicht. Dafür konnte ich einige komplizierte Rätsel mit dem neuen Ansatz deutlich schneller lösen. Leider hatte der hochoptimierte Code auch zur Folge, dass nur noch die Standard-Sudokus mit 9×9 unterstützt wurden. Für die größeren Rätseltypen wäre der Ansatz sehr wahrscheinlich extrem schneller als der aktuelle, aber auch kaum noch zu überschauen. Im Endeffekt war schon der 9×9-Code so ekelig unübersichtlich geworden, dass ich da nur dann irgendwann mal wieder weitermache, wenn ich “viel zu viel” Zeit habe ;)

    An der hier veröffentlichten Version hatte ich allerdings im Sommer/Herbst letzten Jahres weiterprogrammiert. Da kamen einige kleinere Änderungen rein, ein Bug (automatisches Speichern der Lösungen) wurde behoben und eine neue Logikroutine kam hinzu. Letztere führt im Gesamtschnitt allerdings auch wieder zu schlechteren Ergebnissen, weil die Logik nur in weniger als 1% der Sudoku-Rätsel weiterhilft. Die Version müsste ich gelegentlich trotzdem veröffentlichen, mir fehlt nur grad die Lust, das auch für die verschiedenen Plattformen zu tun :) Kommt aber …

    Beste Grüße prote

Einen Kommentar schreiben