Combine is an OCaml library for combinatorics problem solving formed by several modules:

  • Dlx: implements Knuth's dancing links
  • Zdd: implements Zero-suppressed binary decision diagrams
  • Emc: a common interface to modules Dlx and Zdd to solve the Exact Matrix Cover problem
  • Tiling: converts a 2D tiling problem into an EMC problem

  • Several combinatorics problems can easily be encoded as EMC problems, e.g. Sudoku or N-queens.

    Combine also contains an interpreter for a language (combine) to describe 2D tiling problems (such as Pentominos) and solve them or counting their solutions. The archive contains some examples.