Direkt zum Inhalt

Fachbereich Ingenieurwissenschaften und Kommunikation

Programmierung eines parallelen Sudokulösers in VHDL mit Interface und Realisierung auf einem FPGA mit angeschlossenem Touchscreen

Hier finden Sie Informationen zur Programmierung eines parallelen Sudokulösers in VHDL mit Interface und Realisierung auf einem FPGA mit angeschlossenem Touchscreen.
Masterprojekt Elektrotechnik - Schwerpunkt Elektrotechnische Systementwicklung

KURZBESCHREIBUNG:

Seit einigen Jahren sind die in Japan sehr beliebten Sudoku-Rätsel auch in Deutschland weit verbreitet. Ziel ist es, ein 9x9 Zahlenschema so zu ergänzen, dass in jeder Zeile, jeder Spalte und in jedem 3x3-Kästchen jede Ziffer von 1 bis 9 genau einmal vorkommt.

Sie sollen untersuchen, in wie weit sich eine hochgradig parallel arbeitende Hardware zum automatischen Lösen der Rätsel oder einer Klasse der Rätsel entwickeln lässt, und diese dann auf einem FPGA-Board  realisieren. Dazu gehört eine Benutzerschnittstelle auf einem Touchscreen, um eine bequeme Ein- und Ausgabe der Rätsel zu ermöglichen.

Die wichtigsten Aufgaben sind:

  • Recherche der Lösungsstrategien

Sie sollen recherchieren, welche Strategien bei der Lösung von Sudokus eingesetzt werden und in welcher "Situation" diese jeweils geeignet sind.

  • Klassifizierung der Rätsel

Die Rätsel sollen nach Sichtung der Strategien zur Lösung klassifiziert werden. Bei einfachen Sudokus reicht eventuell schon die wiederholte Analyse einzelner Zeilen, Spalten und 3x3-Kästchen aus, um zu einer Lösung zu gelangen. Bei anderen Sudokus sind zur Lösung mehrere Felder gemeinsam zu betrachten. Gegebenenfalls müssen ein oder mehrere Felder mit einem der noch möglichen Werte gesetzt werden, um mit dieser Hypothese weiter zu arbeiten. Ein Sudoku kann eindeutig lösbar sein oder mehrere Lösungen erlauben. Diese Ansätze sollen erweitert und systematisiert werden, um zu einer Klassifizierung zu gelangen. Ziel der Klassifizierung ist es, daraus Aussagen abzuleiten, welche Lösungsstrategien notwendig sind, um Sudokus einer bestimmten Klasse zu lösen.

  • Realisierung  mehrerer Lösungsstrategien in Hardware

Einige Lösungsstrategien sollen in Hardware realisiert werden. Als erster Schritt soll ausgearbeitet werden, wie Sudokus und der im jeweiligen Bearbeitungsschritt aktuelle Lösungsraum in einem FPGA (binär) dargestellt werden können. Außerdem ist zu untersuchen, wie die Strategien, die realisiert werden sollen, möglichst parallelisiert abgearbeitet werden können. Bei einer weitgehend parallelisierten Abarbeitung ergibt sich auf einem FPGA sehr schnell eine Lösung im Vergleich zur weitgehend sequentiellen Abarbeitung auf einem Mikroprozessor.

Parallelisierung erfordert relativ viel Platz auf einem FPGA, sodass der Platzbedarf frühzeitig abgeschätzt werden soll, um eine Realisierung zu ermöglichen.

Parallel zu diesen Aspekten soll eine geeignete Benutzerschnittstelle konzipiert und umgesetzt werden. Ein Touchscreen zum Anschluss an ein FPGA-Board soll dabei genutzt werden.

Diese Arbeit ist besonders geeignet, wenn Sie gerne tüfteln, sich theoretische Hintergründe erarbeiten und die Ergebnisse zudem praktisch umsetzen wollen.


PROJEKTPHASEN:

Masterprojekt 1: Analyse und Beschreibung von Lösungsstrategien für Sudokus und deren Kategorisierung; Konzeptionierung der Benutzerschnittstelle.

Masterprojekt 2: Umsetzung der Lösungsstrategien in parallisierbare Algorithmen unter Berücksichtigung der Größe üblicher FPGAs. Konzeptionierung und (Teil)programmierung der Bildschirmansteuerung.

Masterthesis: Programmierung der Algorithmen und der Bildschirmansteuerung in VHDL und deren Verifikation.

Anzahl Plätze: 2