Skip to content
This repository


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Binary decision diagram library (Lua)

branch: master

Fetching latest commit…


Cannot retrieve the latest commit at this time

Octocat-spinner-32 bdd.lua
Octocat-spinner-32 test.lua

This is a Lua implementation of a binary decision diagram library, as described in Henrik Reif Andersen's "An Introduction to Binary Decision Diagrams". For usage examples, look at the test suite (which depends on lunatest).

The code is written for clarity rather than performance (though it does find all solutions for 10-queens within a couple seconds). I've been studying BDDs and their application to binary constraint solvers, Datalog, and the like. Perhaps it will be helpful to someone else.

If you want more info about BDDs, there's lots of info in Knuth's The Art of Computer Programming vol. 4A, as well as some coverage in Aho, Sethi, and Ullman's Compilers: Principles, Techniques, and Tools 2nd ed.

Something went wrong with that request. Please try again.