HOME | DEUTSCH | IMPRESSUM | KIT

Task Description: Sudoku

Zurück zur Übersicht

Ihre Aufgabe ist die Implementierung eines Sudoku-Spiels für Smartphones mit Hilfe der Android Plattform. Sudoku ist ein aus den 80er Jahren stammendes, mittlerweile sehr populäres Logikrätsel, für das es eine ganze Reihe von Lösungsalgorithmen gibt. Ihr Programm soll eine digitale Version des Rätsels sein, welches eine intuitive und komfortable Bedienung sowie einen fortgeschrittenene Lösungsalgorithmus entählt. Weitere Features des Programms sind von Ihnen frei wählbar.

Vorbemerkung

Dies ist ihr Projekt. Dieses Dokument ist kein Katalog von Aufgaben, der Punkt für Punkt abgearbeitet werden muss, um nachher den Schein zu bekommen, sondern lediglich eine Reihe von Hinweisen, was wir erwarten. Wie ihr Programm nachher aussieht, müssen Sie selbst entscheiden.

Aufgabenstellung

Bestandteile

Das von Ihnen zu erstellende System soll eine Model-View-Controller Architektur verwenden:

  • Ein Model, welches eine Repräsentation des Sudokus, den Lösungsalgorithmus und eine Funktion, die ein neues Sudoku für ein neues Spiel kreiert, enthält.

  • als View ein GUI, das ein Sudoku anzeigt und das manuelle sowie automatische Lösen des Rätsels erlaubt und dem Benutzer Hilfestellung für den nächsten Zug geben kann. Hier ist ihre Kreativität gefragt, da das GUI intuitiv bedienbar sein sollte. Zu berücksichtigen sind, z.B. Anzeige der Hilfestellung, Auswahlfenster für mögliche Zahlen / Symbole oder Zoom-Funktion bei großen Rätseln und kleinem Display

  • einen Controller für die Tasten- und Gesteneingaben des Handys

Das Programm soll in der Simulationsumgebung von Android laufen. Diese Umgebung kann ein Smartphone emulieren, in dem ihr Programm ablaufen soll. Beachten Sie, dass damit die Eingabe auf die vom Simulator bereitgestellten Interaktionsmöglichkeiten beschränkt ist. Es ist aber durchaus erlaubt, zusätzlich komfortabler Eingabemöglichkeiten für echte Smartphones zu implementieren.

Algorithmus

Zur Lösung eines Sudokus existieren mittlerweile eine große Zahl von Algorithmen. Sie sollten, um dem Benutzer eine nachvollziehbare Schritt-für-Schritt Hilfefunktion bieten zu können, einen Algorithmus implementieren, der auf Constraint-Saturation basiert.

Außerdem soll ein alternativer Lösungsalgorithmus (bspw. Branch and Bound Heuristic) implementiert werden. Die Architektur soll generisch genug sein, dass Performance-Vergleiche zwischen den Lösungsalgorithmen gemacht werden können.

Minimale Leistungsmerkmale

Folgende minimale Leistungsmerkmale soll Ihr Programm erfüllen:

  • muss in der Simulationsumgebung von Android laufen und komplett über die dort simulierten Eingabemöglichkeiten bedienbar sein (ohne Multitouch)

  • eine modulare Architektur nach dem Model-View-Controller-Prinzip besitzen

  • eine ‘Generieren’-Funktion enthalten, die ein zufälliges Sudoku erzeugt

  • verschiedene Sudoku-Varianten unterstützen (z.B. 12x12 oder 16x16 oder Hyper-Sudoku oder Killer-Sudoku)

  • ein GUI anzeigen, in dem man ein gegebenes Sudoku manuell, vollautomatisch und halbautomatisch durch Hilfefunktion lösen kann.

  • Implementierung eines Lösungsalgorithmus für Hilfe-Funktion mit Branch-and-Bound und Constraint-Saturation

  • eine ‘Undo-Redo’-Funktionalität besitzen

Android

Android existiert mittlerweile in der Version 4.4 (Kit Kat), allerdings sind auch ältere Versionen noch recht verbreitet. Sie sollten Android 4.2 oder neuer (API level 17+) unterstützen, da dies auch von den Google Play for Education Guidelines empfohlen wird. Optional kann auch Android 2.3 (Gingerbread) unterstützt werden, welches immer noch 20% Marktanteil hat. Das übliche Interface für Android ist Touch, weshalb dieses auch unterstützt werden muss. Andere Modi sind optional.

Bewertung

Die Benotung Ihres Systems richtet sich nach folgenden Kriterien:

  • Qualität aller abgegebenen Dokumente

  • Qualität der Kolloquien

  • Qualität der Abschlusspräsentation

  • Erfüllung der minimalen Leistungsmerkmale (s.o.)

  • sinnvolle Erweiterungen über diese Merkmale hinaus

  • Robustheit des erstellten Programms

Diese Liste hat keine Reihenfolge, die einer Gewichtung entspricht. Es gibt sicherlich weitere Punkte, die als selbstverständlich gelten und sich bei Nichterfüllen negativ auswirken (z.B. ist die Geschwindigkeit der implementierten Algorithmen sekundär, aber jedem sollte klar sein, dass das Errechnen einer Lösung oder das Generieren nicht 10 Minuten dauern darf).

Weitere Pflichten

  • Anmeldung per Studienportal für PSE und TSE

  • Anwesenheit bei den wöchentlichen Treffen mit dem Betreuer

  • Team-internes Management (z.B. Phasenverantwortliche, Versionskontrolle)

  • Artefakte 1–2 Tage vor Kolloquium beim Betreuer

Organisatorisches

Für jede Phase des Praktikums muss ein Phasendokument abgegeben werden. Dieses Dokument ist Grundlage für das Kolloquium am Ende jeder Phase, in dem die Gruppe die Ergebnisse der Phase vorträgt.

Erste Schritte

  • Einarbeitung Android: http://developer.android.com
    Je besser man sich mit Android auskennt, desto besser wird der Entwurf und desto reibungsloser die Implementierung.

  • Werkzeuge sichten:
    Versionsverwaltung mit Subversion oder Git? Eclipse als IDE oder das experimentelle Android Studio (IntelliJ IDEA)? Dokumente mit LaTeX oder Office schreiben? UML-Diagramme?

  • Funktionale Anforderungen überlegen:
    Markt sichten, Muss-Kriterien, Wunsch-Kriterien und Abgrenzungs-Kriterien.

  • Tipps-Dokument lesen!

Literatur

Wir empfehlen folgende Quellen zur Vorbereitung auf die Aufgabe.