Code

• A C++ implementation of the polynomial-time algorithm due to Bulatov and Dalmau for solving constraint-satisfaction problems whose constraints are closed by a Mal'tsev operation.

  Here is the source code.

  Here are 5 very small test-cases: op0.dat, op1.dat, op2.dat, op3.dat, and op4.dat. All five test cases are toy examples of systems of linear equations on the integers modulo 3. The last test case is unsatisfiable. See op0.txt, op1.txt, op2.txt, op3.txt, and op4.txt for the descriptions of the systems. See format.txt for the description of the input format.

  To compile the program, type `g++ maltsev.1.1.cc`. This generates an executable file a.out. To run it on example op2.dat, say, type `a.out < op2.dat`. The output appears in the standard output.

  The implementation is not particularly tuned for efficiency. The only motivation I had for implementing the algorithm was to understand it better.

Back to my home page.