use Language::Prolog::Yaswi qw(:load :query);
use Language::Prolog::Sugar vars => [qw(A B C D E F)],
                            functors => [qw(problem)];

swi_inline <<EOP;

:- use_module(library(clpfd)).

problem(Vars) :-
    Vars = [A, B, C, D, E, F],
    Vars ins 0..1,
    A + E #=< 1,
    A + B #=< 1,
    C + E #=< 1,
    D + F #=< 1,
    B + D #=< 1,
    A + C + E #>= 1,
    B + D #>= 1,
    E + F #>=  1,
    D + F #= 1,
    A + E #=< 1,
    C + D #=< 1,
    A + B + C + D + E + F #= 3,
    label(Vars).

EOP

swi_set_query(problem([A, B, C, D, E, F]));
while (swi_next) {
    my @r = swi_vars(A, B, C, D, E, F);
    print join(', ', @r), "\n";
}

# prints:
# 0, 1, 0, 0, 1, 1
# 0, 1, 1, 0, 0, 1
[download]

Searching CPAN for simplex lists at least two implementations, PDL::Opt::Simplex and Algorithm::Simplex.

So you're in luck, all you have to do is to build the coefficient matrix, call one of the modules, and be happy.

It is not a linear programming problem for at least two reasons. The first is that you're not maximizing a linear function over that search space. The second is that you're not allowed to have fractional numbers in the solution. So a linear algebra package would say that A+B=1, A+C=1 and B+C=1 has a solution, but that would not be a valid solution to the requested problem.

The first is that you're not maximizing a linear function over that search space

That's not a problem, since artist is looking of any solution, one that maximizes a certain function will do just fine

The second is that you're not allowed to have fractional numbers in the solution.

You're right. I misread can take values only from 0 and 1 as can take values only from 0 to 1.

That said, there is lots of research on how to tackle this kind of problem. A term I'd suggest googling for is "Constraint Satisfaction".

A "LP-based tree search" jumps to mind to solve the IP (Integer Programming) problem. I recall this works well for the general case.

There are many NP complete problems with heuristic solutions that work well for some set of real world inputs. There are also many apparently NP complete problems where you can tackle a reduced form of the problem into something simpler to solve. However none of those solutions work well in the general case.

Nothing off the shelf comes to mind but given a suitable grammar (which judging by your examples would probably need just a few rules(*)) you could get something using Parse::RecDescent building a parse tree fairly easily.

(*) Been a while so it's not the right syntax, but along the lines of: STATEMENT => EXPR OP EXPR, EXPR => TERM OP EXPR | TERM, OP => "<=" | ">=", "=", TERM => /A-Z/ | /\d+/

Perusing the following may help:

• Truth Table
• Math::BooleanEval
• generating random thruth-tables
• Generate a truth table from input string
• parser for evaluating arbitrarily complex boolean function in a string
• A "but" operator.

Well, do you want to solve them algebraic/symbolically or through brute force, i.e. testing all the values ?

In the first case you might use a mathematics package (a free alternative would be gap, for money you can get maple, mathematica, magma,...) and use perl to translate your problem into the language of that package

In the second case it might be better to write the search code in C and only do the parsing in perl as the search space grows fast with the number of variables

For the parsing you might use Parse::RecDescent, but if you never have anything more complicated than what you showed in the example, that would be overkill

If I remember my studies correctly, then this should be a CSP: http://en.wikipedia.org/wiki/Constraint_satisfaction_problem

The Wikipedia page also mentions ideas on how to solve these problems, for example backtracking: http://en.wikipedia.org/wiki/Backtracking