Sudoku Solver
Wir haben einen “Sudoku-Löser” programmiert, der anhand eines Fotos von einem Sudoku-Feld die eingetragenen Ziffern erkennt und anschliessend das Sudoku löst.
Für diese Applikation haben wir die Aufgaben in vier Teilbereiche gegliedert:
- Sudoku und Ziffern erkennen, mittels Bildverarbeitungs-Methoden (Computer Vision)
- Ziffern anhand der Bilder klassifizieren, mittels Convolutional Neural Network (CNN)
- Sudoku lösen, mittels Backtracking Algorithmus
- Webapplikation implementieren, mittels Microsoft Azure
Nachfolgend werden die vier Teile detaillierter beschrieben.
Computer Vision
Mithilfe der OpenCV-Softwarebibliothek führen wir Standardbearbeitungen (Graubild, Gaussche Filter) am Bild durch, um das Sudoku-Feld zu finden. Anschliessend werden im Kantenbild nach zusammenhängenden Konturen gesucht. Die grösste, viereckige Kontur wird als Sudoku-Feld ausgewählt.
In diesem Rechteck wird nach zusammenhängenden Komponenten gesucht. Von den erhaltenen Kandidaten wird ein quadratisches Bild ausgeschnitten für den Zahlenklassifikator.
Klassifikator
Als Klassifikator haben wir einen Convolutional Neural Network (CNN), also ein neuronales Netz, trainiert. Sie finden Anwendungen in vielen Computer Vision Problemen, auch für das Erkennen von computer- oder handgeschriebenen Symbolen haben sie sich bewährt.
Das grösste Problem des ganzen Projekts waren die Daten fürs Training des Netzwerkes. Wir mussten unter anderem das MNIST Datenset mit Ziffern europäischer Handschrift erweitern, um die Missklassifikationsrate so tief wie möglich zu halten.
Backtracking Algorithmus
Um ein Sudoku zu lösen, kann man verschieden vorgehen. Wir wählten die Idee eines Backtracking Algorithmus. Der Algorithmus kann alle möglichen Lösungen eines Sudokus finden, falls dieses mehrere Lösungen zulässt. Der Backtracking Algorithmus ist eine Brut-Force Algorithmus und hat dadurch eine hohe Laufzeit. Für die meisten praktischen Fälle, für welche wir getestet haben, reicht er jedoch aus.
Der Backtracking Algorithmus kann in wenigen Zeilen implementiert werden; es gibt aber andere Sudoku-Algorithmen, welche die Struktur des Spiels besser ausnützen und das Problem schneller lösen.
Webapplikation
Um die ganze Logik für den Benutzer zugänglich zu machen, haben wir eine Single Page Application (SPA) mit React geschrieben und diese auf die Azure Cloud bereitgestellt.
