SigSys15 Sudoku-Löser

Autor: Anika Leinhäuser
Betreuer: Prof. Schneider

Ausschnitt eines Sudoku-Rätsels

Motivation

Sudoku-Rätsel haben in den letzten Jahren rasch an Beliebtheit und Bekanntheit gewonnen. Sie werden nicht nur in Zeitungen oder Zeitschriften regelmäßig abgedruckt, sondern erfahren ebenfalls eine rasante Verbreitung im Web oder als App auf dem Smartphone und Tablet. Doch nicht immer lässt sich ein Sudoku-Rätsel leicht lösen. Es bedarf einiger Übung und einer Entwicklung an Lösungsstrategien. Um gedruckte Sudoku-Rätsel lösen zu können, dient der in dieser Dokumentation vorgestellte Sudoku-Löser. Unter der Verwendung einer IP-Kamera liest das Programm das zu lösende Rätsel ein, löst das Sudoku und trägt die Lösung in das fotografierte Sudoku ein.

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

Abbildung 1: Gantt-Diagramm des Projekts Sudoku-Löser

Abbildung 2: Zeitachse des Projekts Sudoku-Löser

Funktionen des Sudoku-Lösers

Dieser Abschnitt stellt eine Übersicht aller Funktionen des entwickelten Sudoku-Lösers dar, welche im Folgenden stichpunktartig dargestellt sind. Die einzelnen Funktionen werden detailliert im siebten Kapitel beschrieben.

1 Einlesen des Sudoku-Rätsels

1.1 Über eine Webcam (IP-Kamera)

1.2 Aus einem Verzeichnis

2 Identifizieren des Sudoku-Rätsels im Bild

2.1 Entzerren des Bildes

2.2 Zuschneiden des Sudoku-Rätsels (manuell oder automatisch)

3 Lösen des Sudoku-Rätsels

3.1 Identifizieren der vorgegebenen Ziffern

3.2 Lösen des Sudoku-Rätsels

3.3 Eintragen der Lösung in das fotografierte Rätsel

Extras

Aus der Übersicht der Funktionen lässt sich entnehmen, dass über die Aufgabenstellung hinaus, der Sudoku-Löser die Funktion bietet, Sudoku-Rätsel aus einem Verzeichnis einzulesen. Dadurch können nicht nur fotografierte Rätsel gelöst, sondern ebenfalls solche, die beispielsweise über das Web heruntergeladen wurden.

Anmerkung

Aus zeitlichen Gründen erfolgte keine Implementierung eines Echtzeit-Lösung des Rätsels über eine Webcam. Jedoch behandelt der Abschnitt „9 Ausblick“ diese Funktion näher und betrachtet mögliche Schritte zur Implementation dieser.

Besonderheiten

Laut einigen Webseiten soll der finnische Mathematiker Arto Inkala das zurzeit schwierigste Sudoku-Rätsel in einer Entwicklungszeit von drei Monaten entworfen haben. Der in dieser Dokumentation beschriebene Sudoku-Löser ist in der Lage, dieses innerhalb sehr kurzer Zeit zu lösen. Dieses Sudoku-Rätsel ist in den Beispielsudokus des Programms hinterlegt und kann mithilfe des entwickelten Programms gelöst werden .

Lösungen

Das vorliegende Kapitel beschreibt alle realisierten Funktionen des entwickelten Sudoku-Lösers. Im Black-Box-Modell ist eine Übersicht dieser zu sehen, sodass ein erster Einblick gewonnen wird. Entlang der chronoligischen Reihenfolge werden anschließend die Funktion näher dargelegt. Zur Veranschaulichung und besseren Verständlichkeit wird ein Beispiel eines zu lösenden Sudokus begleitend eingeführt. Dadurch soll eine einfache Verfolgung des Rätsels vom Einlesen über das Lösen bis zum Eintragen der Lösung gegeben werden.

Konzept (Black-Box-Modell)

In diesem Unterkapitel erfolgt eine Auseinandersetzung mit dem Black-Box-Modell des Sudoku-Lösers. Das Ziel des Black-Box-Modells liegt einerseits darin, die Idee bzw. den Ablauf des Sudoku-Lösers verständlicher darzustellen sowie andererseits einen Einblick in den Aufbau des Programms zu geben. Entscheidungen, die der Benutzer treffen kann, sind nicht darin dargestellt, damit das Modell überschaubar bleibt. Diese werden aber im Folgenden bei der detaillierten Beschreibung des Modells aufgenommen.

Abbildung 3: Darstellung des Black-Box Modells für die Entwicklung

Auf der rechten Seite ist in der Abbildung 3 das Black-Box-Modell des Sudoku-Lösers zu sehen.

In der Abbildung ist zu erkennen, dass nach dem Programmstart das zu lösende Sudoku eingelesen wird. Dabei hat der Benutzer die Auswahl, ob das Sudoku-Rätsel über eine IP-Kamera oder aus einem Verzeichnis eingelesen werden soll. Anschließend wird das Bild mithilfe des Benutzers entzerrt, sodass auch grobe Entzerrungen wie trapezförmige Aufnahmen verwendet werden können. Neben diesem ist ebenfalls eine Rotation des Bildes möglich, sofern das Bild keine Drehung größer als 5° benötigt. Anschließend wird das Sudoku auf die äußeren Rahmenlinien zugeschnitten, sodass nur die wichtigsten Informationen vorhanden sind. In dieser Funktion besitzt der Benutzer die Möglichkeit, das Sudoku manuell zuzuschneiden oder automatisch zuschneiden zu lassen. Im folgenden Schritt erfolgt das Identifizieren der vorgegebenen Ziffern. Daraufhin löst das entwickelte Programm das Sudoku unter kontinuierliche Überprüfung, ob das Sudoku existent ist. Dadurch können Fehler, wie doppelte Ziffern in einer Spalte oder Zeile erkannt werden. Nach erfolgreichem Lösen des Sudoku-Rätsels findet das Eintragen der Lösung in das fotografierte Sudoku statt. Das Sudoku wird dem Benutzer auf dem Bildschirm mit eingetragener Lösung angezeigt.

Einführung in das Programm

Der Sudoku-Löser wurde in der Matlabversion 2014a programmiert. Verwendete Toolboxen wie bspw. die Image Processing Toolbox werden in dem Header der einzelnen Funktionen aufgeführt.

Dieses Kapitel führt in die Funktinen des Programms ein, indem die Startdatei kurz vorgestellt wird. Um den Sudoku-Löser zu verwenden, reicht es aus nur die Startdatei über Matlab zu öffnen und durchzuführen. Es müssen keine weiteren Dateien geöffnet werden.

Das folgende Listing zeigt einen Programmausschnitt der Startdatei.

%*************************************************************%
%                       Sudoku-Solver                         %
%                 Signalverarbeitende Systeme                 %
%         Studiengang Business and Systems Engineering        %
%                  Hochschule Hamm-Lippstadt                  %
%*************************************************************%
%                                                             %
% Autor:    Anika Leinhäuser                                  %
%                                                             %
% Funktion: Das zu lösende klassische 9x9 Suduko-Rätsel wird  %
%           über eine IP-Kamera fotografiert und in diesem    %
%           Programm gelöst. Die Lösung wird dabei in das     %
%           fotografierte Rätsel in Matlab eingetragen.       %
%                                                             %
%*************************************************************%
% Implementaion:   Matlab R2014a                              %
%                                                             %
% Letzte Änderung: 13.06.2015                                 %
%                                                             %
%*************************************************************%


%% Bereinigen des Workspaces und des Command Windows
clear all
close all
clc

%% Funktionsaufruf zum Fotografieren und Einlesen eines Sudokurätsels
Sudoku_eingelesen = Sudoku_einlesen;

%% Funktionsaufruf zur persepektivischen Entzerrung
[Sudoku_entzerrt] = Sudoku_entzerren(Sudoku_eingelesen);

%% Funktionsaufruf zum Zuschneiden des Sudokurätsels
[Sudoku_zugeschnitten, Punkte] = Sudoku_zuschneiden(Sudoku_entzerrt);

%% Funktionsaufruf zum Identifizieren des Sudokurätsels
[Sudoku_Raetsel, Hoehe_Kaestchen, Breite_Kaestchen, SuchMatrix]  = Sudoku_identifizieren(Sudoku_zugeschnitten);

%% Funktionsaufruf zum Lösen des Sudokurätsels
Sudoku_geloest = Sudoku_loesen(Sudoku_Raetsel);

%% Funktionsaufruf zum Eintragen der Lösung
Sudoku_Loesung_eingetragen = Loesung_eintragen(Sudoku_entzerrt, Sudoku_Raetsel, Sudoku_geloest, Hoehe_Kaestchen, Breite_Kaestchen, SuchMatrix, Punkte);

Wie dem oberen Listing zu entnehmen ist, sind die wichtigen Module in einzelne Funktionen ausgegliedert. Dadurch eröffnet sich der Vorteil des modularen Programmaufbaus. Dadurch erhöht sich die Flexibilität in der Programmentwicklung, Veränderungen können schneller vorgenommen werden. Durch die höhere Anpassungsfähigkeit an neue bzw. geänderte Bedingungen können Module leichter verändert, entfernt, ausgetauscht oder neu gruppiert werden. Des Weiteren ergibt sich dadurch die Option, das Programm mit neuen Modulen schnell zu erweitern. Ein weiterer Vorteil der Modularität liegt in der Übersichtlichkeit, sodass Fehler und Bad Smells in einer kürzeren Zeit erkannt und korrigiert werden.

Einlesen des Sudoku-Rätsels

Nachdem die Startdatei in Matlab ausgeführt wurde, öffnet sich ein Abfragedialog. Der Benutzer hat nun zwischen dem Einlesen des Sudoku-Rätsels über eine IP-Kamera oder aus einem Verzeichnis zu wählen.

Fazit

Das vorliegende Projekt war sehr interessant und erbrachte einen hohen Erfahrungswert. Das Projekt Sudoku-Löser gab nicht nur einen tieferen Einblick in die Bildverarbeitung, sondern auch in die modulare Entwicklung eines Programms, welches aus wichtigen Komponenten zusammengesetzt die oben beschriebenen Funktionen erfüllen muss. Dadurch konnte das bisher erworbene theoretische Wissen nicht nur vertieft, sondern auch lehrreich angewandt werden. Aus diesem Grund ist die Bearbeitung von semseterbegleitenden Projekten im Rahmen der Lehrveranstaltung „Signalverarbeitende Systeme“ im Studiengang „Business and Systems Engineering“ weiterzuempfehlen.

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