Nonograms

Though the general case is NP-complete, instances found in puzzle books are directed at humans, and are also suitable targets for ZDDs.

Let us consider a 5x5 nonogram; it should be clear how to generalize. We have \(5\times 5 =25\) elements in our universe. A set represents a colouring scheme for the nonogram: the cell in row \(r\) and column \(c\) is coloured if and only if \(5r + c + 1\) (where the rows and columns are numbered starting from 0) is a member of a set.

We can easily represent the clues for all the rows. For example, if the first row has the clue "1 2", then the ZDD starts with:

Then for each column, we build a ZDD representing the colourings that satisfy that column’s constraints and intersect with the current ZDD. Constructing a column ZDD is similar to constructing a row ZDD except due to our choice of ordering, we must pad the graph with unimportant nodes whose edges both point to the successor node. For example, if the third column has the clue "5", then its ZDD begins with:

Thus a single column ZDD is often at least as big as the ZDD for all rows.

After intersecting all column ZDDs one by one, we should have a ZDD with a unique solution. In general, the size of the ZDDs could increase exponentially during the process, but human-friendly puzzles behave reasonably.

Simple heuristics can give a boost: we should interchange the rows and columns so that the rows are less constrained than the columns, and when iterating through the columns, we should intersect the most constrained columns first.