Nonogrammen Oplossen met DFS en logische regels

Abstract

Een nonogram is een logische puzzel waarbij door het combineren van gegeven cijfers, vakjes in een rooster kunnen worden ingevuld of leeggelaten. Op deze manier kan een plaatje worden onthuld. Omdat nonogrammen kunnen worden gezien als een zoekprobleem, is het niet makkelijk om er met een computer snel een oplossing voor te vinden. [1] stelt twee technieken voor die het mogelijk maken om met een computer de oplossing(en) van een nonogram te vinden. De eerste techniek is Depth First Search (DFS). Dit is een redelijk brute force zoekstrategie. De tweede techniek is subtieler, deze maakt gebruik van logische regels om de zoekruimte te verkleinen. Vervolgens wordt eventueel overgegaan op chronologisch backtracken, waarbij bij elke stap weer geprobeerd wordt om de zoekruimte opnieuw te verkleinen door middel van de logische regels.