This is an implementation of algorithm d3x for finding all the solutions of exact cover problems. d3x accelerates Algorithm DLX by comporessing the input by using Zero-suppressed Binary Decision Diagram. For details, please refer to the paper.
- c++ compiler supporting c++17 (gcc, clang)
- cmake 3.16
$ mkdir build
$ cd build
$ cmake ..
$ cmake -build .$ ./d3x -z zdd_filezdd_filefollows the format of ZDDs used in Graphillion. In graphillion, you can get the ZDD corresponding to a GrpahSet object by usinggs.dump(fp)method.
Masaaki Nishino, Norihito Yasuda, and Kengo Nakamura, "Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams", in Proc. of the 30th International Joint Converence on Artificial Intelligence (IJCAI 21), Paper