Projekte Mathematik / Informatik

Sudoku-Löser 2.0 mit Sudoku-Generator und OCR-Sudoku-Erkennung

Standfoto Demian Rothammel

Ich habe mit Python 3.6 einen Sudoku-Löser mit Sudoku-Generator und OCR-Sudoku-Erkennung programmiert. Basis hierfür war das einfache Sudoku-Lösungsprogramm, das ich 2017 im Schülerwettbewerb SE eingereicht habe und das ich in folgenden vier Aspekten wesentlich weiter entwickeln konnte:

 

  • Erstens kann das Programm im Gegensatz zur Version von 2017 nun alle Sudokus lösen, selbst solche, bei denen nur ein einziger Wert vorgegeben ist.
  • Zweitens kann es nicht nur eine mögliche Lösung finden, sondern alle, wobei ich, um die Laufzeit einzugrenzen, die Ausgabe auf eine vom Benutzer vorgegebene maximale Anzahl von Lösungen beschränkt habe.
  • Ein drittes Problem der Vorgängerversion – die umständliche manuelle Zahleneingabe – konnte ich ebenfalls beheben: Bei der Dateneingabe ermöglicht die neue Version alternativ zur manuellen Eingabe das Einlesen aus einer Bilddatei des zu lösenden Sudokus. Hierfür habe ich Open-CV verwendet um das Sudoku im Bild zu erkennen und die Ziffern einzulesen
  • Und viertens habe ich das Programm um einen Sudoku-Generator erweitert, der Sudokus mit verschiedenen, vom Benutzer gewählten Schwierigkeitsgraden erzeugen kann.

Die Programmlogik greift auf drei Strategien zurück: Erstellen von Kandidatenlisten, scannen und ausprobieren. Insbesondere der letztgenannte Schritt musste wesentlich verändert werden, um das erweiterte Backtracking, sowie das Finden mehrerer Lösungen zu ermöglichen. Nachdem ein Sudoku gelöst wurde, wird ein Richtigkeitscheck durchgeführt und das Ergebnis, die einzelnen Zwischenlösungsschritte sowie der Schwierigkeitsgrad ausgegeben. Wenn das Programm Sudokus erstellt, wird das ungelöste Sudoku und die dazugehörige Lösung ausgeben, sowie der Schwierigkeitsgrad und die zum Erstellen gehörigen Zwischenschritte.

Das Programm löst z.B. ein extrem schweres Sudoku, das viele Lösungsalternativen hat, in 0,6 Sekunden. Um 10.000 Lösungen für dieses Sudoku zu berechnen, benötigt es 3 Minuten und 12 Sekunden.

Forscher: | Demian Rothammel |
Fachgebiet: Mathematik / Informatik
Regionalwettbewerb: Oberfranken