---
title: "Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams"
authors:
  - "Masaaki Nishino"
  - "Norihito Yasuda"
  - "Kengo Nakamura"
doi: "10.24963/ijcai.2021/275"
url: "https://ijcai.org/proceedings/2021/275"
pdf: "https://ijcai.org/proceedings/2021/0275.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1996-2004"
track: "Main Track"
keywords:
  - "Knowledge Representation and Reasoning: Knowledge Representation Languages"
  - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation"
---

# Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams

Masaaki Nishino, Norihito Yasuda, Kengo Nakamura

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1996-2004. DOI: [10.24963/ijcai.2021/275](https://doi.org/10.24963/ijcai.2021/275)

## Abstract

Exact cover refers to the problem of finding subfamily
F of a given family of sets S whose universe
is D, where F forms a partition of D. Knuth’s Algorithm
DLX is a state-of-the-art method for solving
exact cover problems. Since DLX’s running
time depends on the cardinality of input S, it can be
slow if S is large. Our proposal can improve DLX
by exploiting a novel data structure, DanceDD,
which extends the zero-suppressed binary decision
diagram (ZDD) by adding links to enable efficient
modifications of the data structure. With DanceDD,
we can represent S in a compressed way and perform
search in linear time with the size of the structure
by using link operations. The experimental results
show that our method is an order of magnitude
faster when the problem is highly compressed.