TAOCP 7.2.2.1 Exercise 265
We consider Algorithm Z as described in Section 7.
Section 7.2.2.1: Dancing Links
Exercise 265. [22] Prove that Algorithm Z will never produce identical ZDD nodes $(\bar{o}_i ? l_i : h_i)= (\bar{o}_j ? l_j : h_j)$ for $i \ne j$, if all items are primary. But secondary items can cause duplicates.
155
156 COMBINATORIAL SEARCHING 7.2.2.1
Thousands of fascinating recreational problems have been based on polyominoes and their polyform cousins (the polycubes, polyiamonds, polyhexes, polysticks, . . . ). The following exercises explore “the cream of the crop” of such classic puzzles, as well as a few gems that were not discovered until recently.
In most cases the point of the exercise is to find a good way to discover all solutions, usually by setting up an appropriate exact cover problem that can be solved without taking an enormous amount of time.
Verified: no
Solve time: 27m06s
Solution
We consider Algorithm Z as described in Section 7.2.2.1. It constructs a ZDD representing all exact covers of a given problem. The algorithm maintains a dancing‑links structure with primary items (which must be covered exactly once) and possibly secondary items (which may be covered at most once). At each recursive step it chooses an active primary item (i) (using the MRV heuristic with a deterministic tie‑break), then iterates over the options that contain (i). For each such option (O) it covers all items in (O), recurses, and then uncovers. The ZDD node created for the decision at item (i) has the form ((\bar{o}_i;?;l_i : h_i)) where (\bar{o}_i) denotes the primary item (i) (the bar indicates that the item is primary), (h_i) is the ZDD obtained by choosing a particular option covering (i), and (l_i) is the ZDD obtained by skipping that option (i.e., by trying the next option for (i)).
Key observation. When all items are primary, the set of active items completely determines the set of active options: an option is active iff all its items are still active. Moreover, the recursive behaviour of Algorithm Z is a deterministic function of the current set of active items (the MRV choice and the order of options depend only on that set). Consequently, each set of active primary items is encountered at most once during the entire execution. To see this, suppose two different computation paths reached the same set (S) of active items. The first path covers a collection of options whose union is (U); the second covers a different collection whose union is also (U). Since all items are primary, the options in each collection are pairwise disjoint, so both collections are exact covers of (U). But the algorithm’s item choices are determined solely by the current active set. Starting from the full set, the first item chosen is the same in both paths; after covering an option containing that item, the new active set is again the same for both paths, and the next choice is forced to be the same, etc. By induction the sequences of choices must be identical, contradicting the assumption that the collections of options differ. Hence no set of active items is visited twice.
Because a ZDD node is created precisely when the algorithm returns from processing a set of active items, and the triple ((\bar{o}_i, l_i, h_i)) is a function of that set, distinct nodes receive distinct triples. Therefore Algorithm Z never produces two different nodes with the same ((\bar{o}_i;?;l_i : h_i)).
Secondary items break this property. Secondary items need not be covered. Two different computation paths may cover different sets of secondary items while leaving exactly the same set of primary items active. The active options then differ only in whether they contain already‑covered secondary items, but those options are already removed from consideration. The residual problem (active primary items + remaining options) can therefore be identical, causing the same ZDD triple to be generated from two distinct states. For example, let primary items be ({a,b}), secondary items ({c}), options ({a,c}) and ({b}). Choosing ({a,c}) covers primary (a) and secondary (c); choosing ({b}) covers primary (b). Both leave the residual problem with primary item ({b}) (or ({a}) in the first branch) but the ZDD node for the secondary item (c) can be created twice with the same triple.
This completes the proof. ∎