nw  

Generierung von Logikrätseln

Zusammenfassung

Im Auftrag der Rätsel Agentur AG wurde das Mosaik-Rätsel untersucht - ein eher unbekanntes und mehrheitlich unerforschtes Rätsel. Es wurde ein performanter Generator für Mosaik-Rätsel zur Veröffentlichung in Web oder Druckmedien entwickelt.

Schlüsselbegriffe

Java, Effiziente Algorithmen, ILP, Evolutionäre Algorithmen, Constraint Programming, Backtracking


Ausgangslage

Die Rätsel Agentur AG produziert verschiedenste Wort- und Logik-Rätsel für dedizierte Rätselhefte sowie für Zeitungen wie 20 Minuten, Blick am Abend, etc. Um die Wüuml;nsche der Kundschaft gerecht zu werden, sollen möglichst viele Rätseltypen In-House generiert werden. Im Rahmen eines KTI-Projekt entwickelt das Institut für 4D Technologien ein Framework für die Generierung solcher Rätsel, welche sowohl im Web als auch in Druckmedien veröffentlicht werden.

Zielsetzung

Das Mosaik-Rätsel soll hinsichtlich folgender Aspekte analysiert werden:

Ergebnisse

In einer detaillierten Analyse wurden Regeln für das Lösen des Mosaik-Rätsels erkannt, welche dem Auftraggeber bisher noch unbekannt waren. Dem menschlichen Vorgehen beim Lösen eines Mosaik-Rätsels nachempfunden, wurde ein Ansatz zur Klassifizierung definiert. Die erkannten Regeln wurden in einen Lösungsansatz eingearbeitet. Alle zur Verfügung gestellten Rätsel der Rätsel Agentur AG konnten mit diesem, einem Constraint Programming sowie einem ILP-Ansatz gelöst werden. Für die Generierung wurden zwei Ansätze entwickelt: Ein Generator basierend auf Backtracking (Fokus Performanz) sowie Generator basierend auf Evolutionären Algorithmen (Fokus minimale Anzahl Hinweise). In einem dritten experimentellen Ansatz wurde aufgezeigt, wie die Generierung vom Mosaik-Rätseln mittels IPL umgesetzt werden könnte.

Projektdaten
Projektart Projektarbeit 8. Semester
Projektdauer 1 Semester
Aufwand 720 Personenstunden
Teamgrösse 2 Personen

Projektteam

Melanie Erb
Studentin Informatik (berufsbegleitend)
8. Semester
melanie.erb@students.fhnw.ch


Nicolas Portmann
Student Informatik (berufsbegleitend)
8. Semester
nicolas.portmann@students.fhnw.ch

Projektbetreuer

Prof. Dr. Manfred Vogel
manfred.vogel@fhnw.ch


Stephen Randles
stephen.randles@fhnw.ch

<< zurück