Sudoku

In theory, we could scale up our toy example to represent sudoku puzzles. Instead of 3 kinds of fruit over 2 days, we have 9 possible digits in 81 squares. For each square, we find a ZDD representing all sets with exactly one digit in that square. Intersecting these ZDDs produces a ZDD \(A\) representing all sets where there is exactly one digit per square.

We then find ZDDs representing each sudoku condition. For instance, we will need the ZDD containing all sets where there is exactly one 1 in the top row. We intersect these with \(A\) to produce a ZDD \(B\) that represents the family of all valid ways to fill in a blank sudoku puzzle.

Sadly, the family of valid sudoku solutions is a good example of a family that is hard to represent with ZDDs. No matter how we order the elements, the membership of some low-numbered elements will have a large effect on the membership of many high-numbered elements in such a way that the ZDD will contain too many nodes to compute with.

The BDD for multiplication can be shown the require many nodes no matter what ordering is chosen. This ought to also hold for sudoku and latin squares. At the very least, even if efficient orderings exist, finding them is NP-hard.

We might hope that 729 variables are still few enough to be conquered by ZDDs. Suppose we take the obvious route, so that 81 r + 9 c + d represents the digit d in row r and column c. The start is promising: it is easy to write down a 731-node ZDD representing the sets of all 9x9 grids with exactly one digit in each box. Next, adding the 81 conditions requiring each digit appear exactly once in each row gives a ZDD of size 20738.

Adding the 81 conditions requiring each digit appear once in all nine 3x3 regions increased the ZDD size to 2870264 nodes (there are \(852267027045566343530110865375232000 = 9!^3 (9^{\frac{3}{}})^3 9^6\) solutions satisfying the conditions so far).

But the one-digit-per-column rules add an unmanageable number of nodes. Sometimes a single column constraint roughly doubles the nodes, and there are 81 of them. For example, after requiring the digit 1 to appear exactly once in the first column, the ZDD balloons to 4746198 nodes. (There are \(378785345353585041568938162388992000 = 4 \cdot 10^3 9^{14} 8^{15} 7^6\) solutions).

If we have a partially solved puzzle, we could start from a ZDD representing the family of sets that contain the given entries, and feasibly compute the intersections described above to find the set of all solutions, but we may as well use other methods such as dancing links.

ZDDs are better suited for problems where an element only influences a few other elements in its vicinity, in other words, we can number the elements in such a way that most of the time, the membership of a given element is only related to the membership of closely-numbered elements.