Light Up

Human-friendly Light Up puzzles are also ZDD-friendly. We start with one element for each location where a light bulb may be placed. Then for each row, we construct the ZDD of sets containing at most one of the elements in the row. Similarly for columns.

Next, for each blank square, we construct the ZDD of sets containing at least one element that can be reached in a single rook move from that square.

Lastly, for each number \(n\), we construct the ZDD of sets containing exactly \(n\) elements in the square surrounding that number.

The intersection of these ZDDs are the solutions.

As these puzzles resemble the eight queens puzzle, carefully written recursive search algorithms can probably solve them much quicker than a ZDD could. However, it is much easier to write a ZDD solver, provided the basic routines have already been implemented. Also, for smaller sizes, we can answer questions about incomplete puzzles. For example, given only a few or even none of the clues, how many solutions are there? How do we pick one at random? Which has maximum weight, where a light bulb in row \(x\) and column \(y\) is worth \(x + y\)?


Ben Lynn blynn@cs.stanford.edu 💡