SigSys15 Sudoku-Löser

Autor: Anika Leinhäuser
Betreuer: Prof. Schneider

Ausschnitt eines Sudoku-Rätsels

Motivation

Ein gedrucktes Sudoku-Rätsel soll gelöst werden, indem ein Matlab-Programm über eine Webcam (IP-Kamera) das Rätsel einliest und die Lösungen darin einträgt.

Ziel

Das zu lösende klassische 9x9 Suduko-Rätsel soll fotografiert und in Matlab gelöst werden. Die Lösung soll dabei in das fotografierte Rätsel von Matlab eingetragen werden.

Aufgabe

1. Einarbeitung in die Schrift- und Linienerkennung
2. Einlesen des Sudoku-Rätsels, sodass alle Ziffern über die Bildverarbeitung von Matlab erkannt und verwendet werden können
3. Identifikation des Rätsels im Bild
4. Perspektivische Entzerrung
5. Untersuchung verschiedener Ansätze zur Erkennung der Zahlen (z.B. Template Matching gegenüber modelbasierten Ansätzen)
6. Umsetzung eines Algorithmus zur Lösung des Soduko-Rätsels
7. Zusammenführung des Erkennungsalgorithmus und des Lösungsalgorithmus

Kür: Echtzeit-Lösung des Rätsels über die Webcam inkl. perspektivische Verzerrung (vgl. YouTube Video)

Hinweis: Eine Kopie der Lösung von Mathworks ist nicht zulässig.

Einleitung

Im Rahmen der Lehrveranstaltung „Signalverabeitende Systeme“ des Studiengangs „Business and Systems Engineering“ im Sommersemester 2015/16 gab es die Aufgabe, ein semesterbegleitendes Projekt im Bereich der Signal- und Bildverarbeitung in Matlab durchzuführen. Die vorliegende Dokumentation befasst sich mit einem Sudoku-Löser.

Detailliert bestand die Aufgabe darin, sich in die Schrift- und Linienerkennung einzuarbeiten und das gewonnene Wissen für die Implementierung des Sudoku-Lösers anzuwenden. Dabei soll der Sudoku-Löser die Funktion bieten, ein Sudoku-Rätsel einzulesen, wobei über die Bildverarbeitung die vorgegebenen Ziffern erkannt und verwendet werden können. Dazu sollte eine Identifikation des Rätsels im Bild sowie eine perspektivische Entzerrung erfolgen. Darauf aufbauend galt es, unterschiedliche Ansätze zur Erkennung der Ziffern zu untersuchen. Über die Umsetzung der Ziffernerkennung hinaus beinhaltete die Aufgabe die Implementierung eines Algorithmus zur Lösung des Sudoku-Rätsels. Nach erfolgreicher Implementation des Erkennungs- und des Lösungsalgorithmus galt es, diese zusammenzuführen. Der letzte Schritt beinhaltete neben einer kontinuierlichen Verbesserung des Programms ein abschließendes Testen aller Funktionen des Sudoku-Lösers.

Die Dokumentation des Sudoku-Lösers und eine Live-Vorführung in Form eines Youtube-Videos stellten ebenfalls Erwartungen dar.

Konzept (Projektplanung)

Die folgenden Punkte geben das Projektkonzept stichwortartig wieder:

0 Festlegung des Projektthemas innerhalb der Lehrveranstaltung „Signalverarbeitende Systeme“

1 Projektvorbereitung

1.1 Recherche von Informationen zur Aufgabenstellung

1.2 Organisation und Planung der anstehenden Aufgaben

1.3 Intensive Einarbeitung in die Schrift- und Linienerkennung

2 Projektdurchführung

2.1 Detaillierte Konzepterstellung (Programmidee als Black-Box-Modell entwerfen)

2.2 Entwicklung des Einlesealgorithmus

2.3 Entwicklung einer Funktion zur Identifikation des Rätsels im Bild

2.4 Implementation eines Algorithmus zur perspektivischen Entzerrung

2.5 Untersuchung verschiedener Ansätze zur Erkennung der Ziffern

2.6 Implementierung eines Algorithmus zur Identfikation der Ziffern

2.7 Umsetzung eines Algorithmus zur Lösung des Soduko-Rätsels

2.8 Zusammenführung des Erkennungsalgorithmus und des Lösungsalgorithmus

2.9 Testen der Funktionen des Sudoku-Lösers und ggf. Durchführung von Verbesserung

3 Projektabschluss

3.1. Auswertung des Projekts

3.2. Abschließen der Dokumentation

Die detaillierte Projektplanung werden durch das Gantt-Diagramm und durch die Zeitachse erfasst, welche mit MS Project 2013 erstellt wurden. Während der Projektzeit (23.03.2015 bis 20.06.2015) erfolgte eine stetige Verfolgung, ob alle Vorgänge und Meilensteine rechtzeitig einghalten wurden. Das Gantt-Diagramm ist im Folgenden in der linken Abbildung dargestellt. Die Zeitachse befindet sich auf dem rechten Bild (siehe Abbildung 2).

Weblinks

• Sudokus lösen mit MATLAB
• Solve Sudoku Puzzles Via Integer Programming
• A Matlab-based sudoku solver
• YouTube: Solving a Sudoku Puzzle Using a Webcam
• YouTube: LEGO Mindstorms Sudoku Solver

---

→ zurück zum Hauptartikel: Signalverarbeitende Systeme SoSe2015