The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours

Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato 14–17] who presents applications for cube set representations, fault simulation, timing analysis and the n-queens problem. Here the structural properties of ZBDDs are worked out and a generic synthesis algorithm is presented and analyzed. It is proved that ZBDDs can be at most by a factor n + 1 smaller or larger than ordered BDDs (OBDDs) for the same function on n variables. Using ZBDDs the best known upper bound on the number of knight's tours on an 8 × 8 chessboard is improved significantly.