An efficient algorithm for solving nonograms

Authors: ChiungHsueh Yu HuiLung Lee LingHwei Chen

Publish Date: 2009/11/13

Volume: 35, Issue: 1, Pages: 18-31

PDF Link

Abstract

Nonogram is one of logical games popular in Japan and Netherlands Solving nonogram is a NPcomplete problem There are some related papers proposed Some use genetic algorithm GA but the solution may get stuck in local optima Some use depth first search DFS algorithm the execution speed is very slow In this paper we propose a puzzle solving algorithm to treat these problems Based on the fact that most of nonograms are compact and contiguous some logical rules are deduced to paint some cells Then we use the chronological backtracking algorithm to solve those undetermined cells and logical rules to improve the search efficiently Experimental results show that our algorithm can solve nonograms successfully and the processing speed is significantly faster than that of DFS Moreover our method can determine that a nonogram has no solution

Keywords: