Dominosa

Like sudoku, Dominosa instances can easily be converted to an exact cover problem (exercise), and thus rapidly solved via the dancing links algorithm.

However, translating it to a ZDD has some advantages for sizes small enough to fit in memory. We can first compute all possible tilings for a given size. Immediately we can count the number of possible Dominosa puzzles, or select one at random, or find the one with maximum weight according to any weighting scheme. Intersecting with appropriate ZDDs allows us to answer more complex questions. For example, how many Dominosa puzzles are there with 0 0 tile in the top left corner? Or with a 3 in a certain location? Enumerating these via dancing links is too costly.