Sudoku Solver
Sudoku Solver
Wir haben einen «Sudoku-Löser» programmiert, der anhand eines Fotos eines Sudoku-Feldes die eingegebenen Zahlen erkennt und dann das Sudoku löst.
Für diese Anwendung haben wir die Aufgaben in vier Teilbereiche aufgeteilt:
- Sudoku und Zahlen mit Bildverarbeitungsmethoden erkennen
- Erkennen von Zahlen mit Hilfe eines KI-Modells
- Lösen von Sudoku mittels Backtracking-Algorithmus
- Implementierung einer Webanwendung mit Microsoft Azure
Im Folgenden werden die vier Teilbereiche näher beschrieben.
Computer Vision
Mit Hilfe der Softwarebibliothek OpenCV führen wir verschiedene Schritte durch, um das Sudoku-Feld zu finden. Zuerst werden typische Vorverarbeitungsschritte (Graubild, Gaußscher Filter) am Bild durchgeführt und nach Kanten gesucht. Anschließend wird im Kantenbild nach zusammenhängenden Konturen gesucht. Die größte viereckige Kontur wird als Sudoku-Feld ausgewählt.
Nachdem das Viereck in ein Quadrat transformiert wurde, wird in diesem nach zusammenhängenden Komponenten gesucht. Diejenigen Komponenten, die bestimmte geometrische Bedingungen erfüllen, werden als Zahlenkandidaten ausgewählt. Für jeden solchen Kandidaten wird ein quadratisches Bild ausgeschnitten, das dem Zahlenklassifikator übergeben wird.
Klassifikator
Als Klassifikator haben wir ein Convolutional Neural Network (CNN), also ein neuronales Netz, trainiert. Diese finden Anwendung in vielen Bildverarbeitungsproblemen und haben sich auch bei der Erkennung von computer- oder handgeschriebenen Symbolen bewährt. Wir haben unser CNN mit dem bekannten MNIST-Datensatz und einem zusätzlichen Satz von Zahlen trainiert. Das zusätzliche Datenset besteht aus handgeschriebenen Ziffern der europäischen Schrift, die sich insbesondere bei den Ziffern 1 und 7 von der angelsächsischen Schrift unterscheidet.
Allerdings war die Fehlklassifikationsrate von Ziffern in einem begonnenen Sudoku (Kombination von computer- und handgeschriebenen Symbolen) so hoch, dass wir unser eigenes Modell nicht weiter verwenden wollten. Daher haben wir auf ein vortrainiertes Modell zurückgegriffen.
Backtracking Algorithmus
Es gibt verschiedene Möglichkeiten, ein Sudoku zu lösen. Wir haben uns für einen Backtracking-Algorithmus entschieden. Dieser Algorithmus ist in der Lage, alle zulässigen Lösungen eines Sudokus zu finden. Der Backtracking-Algorithmus ist ein Brut-Force-Algorithmus und hat daher eine hohe Laufzeit. Für die meisten praktischen Fälle, die wir getestet haben, ist er jedoch ausreichend.
Der Backtracking-Algorithmus kann in wenigen Zeilen implementiert werden, aber es gibt andere Sudoku-Algorithmen, die die Struktur des Spiels besser ausnutzen und das Problem schneller lösen.
Webapplikation
Um die gesamte Logik für den Benutzer zugänglich zu machen, haben wir eine Single Page Application (SPA) mit React geschrieben und auf der Azure Cloud gehostet.
