Dancing with Decision Diagrams: A Combined Approach to Exact Cover

No. 1: Thirty-First AAAI Conference On Artificial Intelligence

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 31

AAAI Technical Track: Heuristic Search and Optimization

Exact cover is the problem of finding subfamilies, S*, of a family ofÊsets, S, over universe U, where S* forms a partition ofÊU. ÊIt is a popular NP-hard problem appearing in a wide range of computerÊscience studies. Knuth's algorithm DLX, a backtracking-based depth-firstÊsearch implemented with the data structure called dancing links, is knownÊas state-of-the-art for finding all exact covers. We propose a method toÊaccelerate DLX. Our method constructs a Zero-suppressed Binary DecisionÊDiagram (ZDD) that represents the set of solutions while runningÊdepth-first search in DLX. Constructing ZDDs enables the efficient use ofÊmemo cache to speed up the search. Moreover, our method has a virtue thatÊit outputs ZDDs; we can perform several useful operations withÊthem. Experiments confirm that the proposed method is up to several ordersÊof magnitude faster than DLX.

10.1609/aaai.v31i1.10662