Solving a simple geometric puzzle in CLPQ/R (Prolog)

Question

Consider the following square:

You are given three constraints:

All rectangles (A, B, C, D and E) have the same area;

Their geometric layout constitutes a square; and

The height of A is 2.

Now, I know this is very simple to solve by hand, but I thought it would be a very good example to show off the capabilities of CLP(Q/R) with Prolog:

SPOILER ALERT: If you want to first solve the puzzle by yourself, do not continue to read this, as there are constraints that will give away the solution.

Anyway, here's my attempt at defining (with I think include redundant constraints) this puzzle with CLP(Q/R):

:- use_module(library(clpr)).

solve(Eh) :-
  A = B, B = C, C = D, D = E,

  { A  >= 1, B  >= 1, C  >= 1, D  >= 1, E  >= 1,
    Aw >= 1, Bw >= 1, Cw >= 1, Dw >= 1, Ew >= 1 },
  
  { Ah = 2 },
  
  { A = Ah * Aw,
    B = Bh * Bw,
    C = Ch * Cw,
    D = Dh * Dw,
    E = Eh * Ew },

  { (Bw + Cw) = Aw,
     Dw = Cw,
    (Ah + Bh) = Eh,
    (Ch + Dh) = Bh,
    (Aw + Ew) = Eh },

  minimize(Eh).

Which when queried:

?- solve(Eh).
false.

...makes me sad. Such a beautiful example for a constraint solver... Anyone cares to undo my sadness?

Addendum: I used Mathematica and the FindMinimum function to check for my constraints. It seems to be working:

domain = a >= 1 && b >= 1 && c >= 1 && d >= 1 && e >= 1 && ah == 2.0 && a == b == c == d == e && aw >= 1 && bw >= 1 && cw >= 1 && dw >= 1 && ew >= 1
rectangles = (a == ah*aw && b == bh*bw && c == ch*cw && d == dh*dw && e == eh*ew)

FindMinimum[{eh, 
  domain && rectangles &&
  ((bw + cw ) == aw && dw == cw && (ah + bh) == eh && (ch + dh) == bh && (aw + ew) == eh)}, 
  {a, b, c, d, e, ah, aw, bh, bw, ch, cw, dh, dw, eh, ew}]

Answers:

{8., {a -> 12.8, b -> 12.8, c -> 12.8, d -> 12.8, e -> 12.8, 
      ah -> 2., aw -> 6.4, bh -> 6., bw -> 2.13333, ch -> 3., 
      cw -> 4.26667, dh -> 3., dw -> 4.26667, 
      eh -> 8., ew -> 1.6}}

I think the problem are the non-linearity of the constraints, i.e. A = Ah*Aw etc. The rules when non linear constraints are allowed in CLP(R) are here: swi-prolog.org/pldoc/man?section=clpqr-non-linear but I'm not sure how to fix this. Note: If you change * to + there will be a result (although not correct). (I wrote a MiniZinc model which confirms you Mathematica result.) — hakank
I agree that this is probably due to the multiplications. Even this fails in CLP(R) and CLP(Q) on my SWI-Prolog 7.2.3: ?- { X >= 1, Y >= 1, Z = X * Y }, inf(Z, Inf). Looks like these libraries are not the right tools for this kind of puzzle. — Isabelle Newbie

CapelliC CapelliC · Accepted Answer · 2020-07-27T18:45:48

There is a old/new entry in CLP, clpBNR. You can install it in a recent version of SWI-Prolog.

I think it would require to group equations together into a single {}.

?- pack_install(clpBNR).

:- use_module(library(clpBNR)).

solve_(Eh) :-
  Vs = [A,B,C,D,E, Aw,Bw,Cw,Dw,Ew, Ah,Bh,Ch,Dh,Eh],
  Vs::real(1,100),

  { Ah == 2,

    A is Ah * Aw,
    B is Bh * Bw,
    C is Ch * Cw,
    D is Dh * Dw,
    E is Eh * Ew,

    A == B,
    B == C,
    C == D,
    D == E,

    (Bw + Cw) == Aw,
     Dw == Cw,
    (Ah + Bh) == Eh,
    (Ch + Dh) == Bh,
    (Aw + Ew) == Eh
  },

  solve(Vs).

?- solve_(Eh).
::(Eh, ...( 8.000000)) .

Solving a simple geometric puzzle in CLPQ/R (Prolog)

1 Answers