Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Consider the following square:

enter image description here

You are given three constraints:

  1. All rectangles (A, B, C, D and E) have the same area;
  2. Their geometric layout constitutes a square; and
  3. 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}}
like image 654
Hugo Sereno Ferreira Avatar asked Jul 27 '20 00:07

Hugo Sereno Ferreira


1 Answers

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)) .
like image 197
CapelliC Avatar answered Nov 14 '22 00:11

CapelliC