Sudoku-Löser-Programmierung (Sudoku-Solver Teil 4)

Mathematische Methoden
Hierbei wird über die Mengenlehre mit entsprechenden Querschnittsmengen eine Liste von Kandidaten für jedes Feld ermittelt. Mit Hilfe der zuvor aufgezählten Strategien lassen sich logische Verknüpfungen erstellen, die weitere Einschränkungen definieren. Die komplexe Logik dahinter wird teils auch dem Bereich der Constraints zugeordnet. Hinter diesem englischen Begriff verbirgt sich allerdings nichts weiter als eine Sammlung sämtlicher Randbedingungen und Logik, die zur Lösung des Rätsels führen. Nicht in diesen Bereich gehören die Probieren-durch-Einsetzen-Methoden für nicht allein logisch lösbare Rätsel.
Führen die Logik-Algorithmen nicht zur Lösung, so kommt die so genannte Backtracking-Methode zum Einsatz, welche durch Einsetzen ermittelter Kandidaten in die freien Felder versucht, das Rätsel zu lösen. Klappt dies nicht im ersten Rateversuch, so erfolgt der Rückschritt (Backtrack) zur Ausgangssituation.

Allgemeines zur Programmierung von Sudoku-Lösern
Ein Sudoku-Löser oder auch Sudoku-Solver kann auf verschiedene Weise programmiert werden. Entweder setzt man die bekannten Lösungsstrategien um und ergänzt evtl. eine Backtracking-Methode für nicht allein logisch lösbare Rätsel oder man versucht gleich über das Backtracking zu einer Lösung zu kommen. Letzterer Ansatz entspricht einem Bruteforce mit allen denkbaren Variationen in den freien Feldern und kann bei ungünstigen Rätseln ohne vorbereitende Maßnahmen (Drehung, Spiegelung) selbst bei den kleinen 3×3-Sudokus recht lange dauern – Angaben von 30-45 Minuten auf „aktuellen“ PCs finden sich hierzu im Internet. Eine Kombination von Logik mit Backtracking hingegen sollte selbst bei schlechter Umsetzung und ungünstiger Ausgangssituation nur wenige Millisekunden dauern.
Als Vergleichswerte kann ich folgende Werte für meinen rein logisch arbeitenden Sudoku-Solver v0.4 auf einem AMD Phenom II X3 720 @ 3.3 GHz mit Win7-64 angeben:
3×3 etwa 150-250 µs
4×4 etwa 400-600 µs
5×5 etwa 1,5-3 ms
Das Tool wurde zwar recht effektiv geschrieben, lässt sich aber mit Sicherheit in Bezug auf die Geschwindigkeit weiter optimieren – die Frage dabei wäre nur: wozu? Die Anzeige der Daten dauert schon jetzt wesentlich länger, als das Lösen des Rätsels. Dennoch ist es eine interessante Herausforderung, derartige Algorithmen weitgehend zu optimieren. Geschrieben wurde der Sudoku-Solver in der OpenSource-IDE Lazarus, also einer zu Delphi verwandten Object-Pascal-Umgebung. Der Quelltext des Sudoku-Solvers steht unter der GPLv2; bei Forks bitte ich aber darum, hierher zu verlinken und mich zu informieren – vielleicht habe ich ja Interesse daran, das Projekt entsprechend weiterzupflegen ;)

2 Reaktionen zu “Sudoku-Löser-Programmierung (Sudoku-Solver Teil 4)”

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

    Für mich ist das Programm nicht verständlich!
    (Habe erst seit einem halben Jahr Informatik in der 10. Klasse.)
    wir haben im Unterricht bisher nur mit Dev Pascal gearbeitet und daher nur wenige Befehle kennengelernt.
    Es wäre toll wenn jemand es mir erklären könnte!

    Edit by prote: Die Sourcen sind zwar an sich recht trivial und für erfahrene Programmierer weitestgehend selbsterklärend, aber wohl kaum für Einsteiger in die Programmierung geeignet. Da solltest Du Dich lieber erst an einfacheren Dingen austoben ;)

Einen Kommentar schreiben