prolog clpfd: creating arithmetic constraints from data

Question

I am trying to solving a set of problems similar to the Einsten problem using prolog.

My input consists of two lists:

A domain list. Ex: [[domain(brand),volkswagen,gm,audi],[domain(country),germany,spain,italy]].
A constraint list: [[=,spain,[+,gm,1]],[=,germany,volkswagen],[=,italy,2]]. It means: spain = gm + 1, germany = volkswagen, italy = 2.

I can solve this problem easily hard coding it:

puzzle(Spain,Italy,Germany,Volkswagen,Gm,Audi,X):-
Country = [Spain, Italy, Germany], ins(Country, 1..X), all_different(Country),
Brand = [Volkswagen, Gm, Audi], ins(Brand, 1..X), all_different(Brand),
Spain #= Gm + 1,
Germany #= Volkswagen,
Italy #= 2.

And calling:

275 ?- puzzle(Spain, Italy,Germany, Volkswagen, Gm, Audi,3).
Spain = Audi, Audi = 3,
Italy = Gm, Gm = 2,
Germany = Volkswagen, Volkswagen = 1.

My questions:

What would be a way to create the domains dynamically from my input data? In this example I only have 2 domains (Country, Brand) but there are another inputs with 5 or 6 domains. Thus, how could I make the number and size of the domains variable?
How could I create the constraints dynamically from the list I have? How to connect the constants from the constraint's list to the variables of the previous question?

In summary, how to build a solver that depends only on the input?

CapelliC CapelliC · Accepted Answer · 2015-10-02T08:44:54

a simple minded translation

puzzle(Ds, Cs, Symbols) :-
    maplist(make_vars, Ds, Syms, Vars),
    append(Syms, Symbols),
    maplist(constraints(Symbols), Cs),
    append(Vars, Store),
    label(Store).

make_vars([domain(_)|Names], NamesVars, Vars) :-
    length(Names, N),
    length(Vars, N),
    Vars ins 1 .. N,
    all_distinct(Vars),
    pairs_keys_values(NamesVars, Names, Vars).

constraints(Symbols, [=, L, R]) :-
    expr(L, Symbols, X),
    expr(R, Symbols, Y),
    X #= Y.

expr(N, _, N) :- number(N).
expr(S, Symbols, X) :- memberchk(S-X, Symbols).
expr([+, L, R], Symbols, X + Y) :-
    expr(L, Symbols, X),
    expr(R, Symbols, Y).

yields

[volkswagen-1,gm-2,audi-3,germany-1,spain-3,italy-2]

Easy generalization of expr/3:

expr([Op, L, R], Symbols, ClpF) :-
    expr(L, Symbols, X),
    expr(R, Symbols, Y),
    ClpF =.. [Op, X, Y].

so it accepts other binary operators. A similar one can be applied to constraints/2 as well:

constraints(Symbols, [Op, L, R]) :-
    expr(L, Symbols, X),
    expr(R, Symbols, Y),
    memberchk((Op, OpC), [(=, #=), (<, #<)]),
    call(OpC, X, Y).

but note the difference: constraints/2 posts the actual constraint, while expr/3 simply translate the syntax tree.

prolog clpfd: creating arithmetic constraints from data

1 Answers