Solving Nonograms: A Constraint Satisfaction Approach

Dieses Kapitel vertieft sich in die komplizierte Welt der Nonogramme, auch als Picross oder Griddlers bekannt, und präsentiert einen bahnbrechenden Ansatz zur Lösung dieser Rätsel mithilfe von Constraint Satisfaction Problems (CSPs). Die Autoren stellen eine neue Methode vor, die das Nonogramm in kleinere, unabhängige CSPs für Zeilen und Spalten zerlegt, die gleichzeitig durch Multiprocessing gelöst werden. Diese Zersetzung vereinfacht die ersten Lösungsschritte erheblich und verbessert die Skalierbarkeit der Lösung, insbesondere bei großen Rätseln. Das Kapitel bietet eine umfassende Literaturübersicht über bestehende Ansätze zur Lösung von Nonogrammen, einschließlich ganzzahliger linearer Programmierung, Tiefensuche und neuronaler Netzwerke, und vergleicht sie mit der vorgeschlagenen Methode. Die Effizienz des CSP-Ansatzes wird durch ein umfassendes Benchmarking mit modernsten Lösern bewertet, die unterschiedliche Datensätze verwenden. Die Ergebnisse zeigen die überlegene Leistung der vorgeschlagenen Technik, die Bitmaskierung und Parallelisierung nutzt, um Rechenkomplexität und Speichernutzung zu minimieren. Das Kapitel schließt mit einer Diskussion zukünftiger Arbeiten, einschließlich der Verfeinerung des Backtracking-Algorithmus und der Entwicklung spezieller CSP-Formulierungen für farbige Nonogramme.