EFC

News

EFC version 1.1.0 has been released. Download it here, view the changes online here and some high level documentation here.

Features

1. Modular definition of algorithms. A great number of algorithms can be implemented by the combination of different modules for constraint propagation and intelligent backtracking. The following modules have already been implemented:
   • Constraint propagation
     • Forward Checking
     • Maintaining Arc Consistency
   • Backtracking
     • Chronological backtracking
     • Intelligent backtracking with CBJ or value-specific CBJ.
   Moreover, with cooperating modules, we can add these features to any combination produced from the above:
   • Nogood recording, which can be unrestricted, length bounded or relevance bounded.
   • Support for generalized nogood discovery (good fun!, check this paper for more), including discovering 1UIP nogoods.
   • Post processing of nogoods using Ulrich Junker's ReplayXPlain algorithm to discover minimal nogoods at the leafs.
2. Various models in the following domains have been implemented
   • Golomb rulers (discovery and proof of minimality)
   • Planning, using Peter van Beek's CPlan.
   • Crossword puzzles, again using Peter van Beek's code. Unfortunately, it is not publically available, so you'll have to mail him if you want to use that.
3. Pluggable constraint propagators.
4. Flexible dynamic variable ordering (DVO) implementation. Both deterministic and non-deterministic DVO's are possible, with most major known ones already implemented (dom+deg, dom/deg, lexicographic.)
5. Detailed logging. Several statistics are kept, including nodes and branches visited, consistency checks performed and cpu time spent. Moreover, additional information can be dumped to disk during or after the search.
6. Designed for experimentation. Even though the code can be used as a library as part of a larger program, there are features that allow the user to just create a model/algorithm/DVO and be able to perform a large number of experiments with it.

Using EFC

Download

1. EFC 1.1.0, the most recent version. Download this if you have no reason to use an older version.
2. EFC 1.0.1, the first official release of EFC.

If you have any questions, comments or bug reports, please drop me an email.

Authors