Modeling symbolic puzzles

Greetings. Just out of curiosity I wanted to test if I could model a set of symbolic problems in Prolog.
I constructed a simple class of problems with the following structure:
First, assume that all four scales in the image are in perfect balance,

Then explore diverse expressions like in_balance([diamond],[circle, triangle, square]) and decide if what the expression says is compatible or contradictory with the previous knowledge.

At first I thought that was a task to be solved with CLPFD, but after a few failed attempts I realized that there could be many different ways of modeling this kind of puzzle.

Can you please show me some of those strategies? I prefer CLP-style solutions but traditional Prolog modeling would be fine too.
Thanks in advance.

How about e.g. (for the 2nd picture):

same_weight([yellow_square, yellow_square], [green_triangle, yellow_square]).

Of course, the order within the lists does not matter.

It would be nice if the program deduced that the weight of green_triangle and yellow_square is same.

The weights could be integers, e.g. red_circle is worth 1, and yellow_square worth 2, and orange_rhombus worth 4.

Of course brebs,

That way of static representation seems adecuate. But I was refering to strategies to solve the puzzle…

Well, in clpfd it could be e.g.:

[YellowSquare, GreenTriangle, OrangeRhombus] ins 1..100,
YellowSquare * 2 #= GreenTriangle + YellowSquare,
OrangeRhombus #= YellowSquare * 2,
once(labeling(
    [min(YellowSquare)], 
    [YellowSquare, GreenTriangle, OrangeRhombus]
)).

Result:

YellowSquare = GreenTriangle, GreenTriangle = 1,
OrangeRhombus = 2
1 Like

That one looks interesting and similar to my previous attempts,
and there I had doubts:

  • Why is it needed to assign numeric values, at least for the first figure?
  • How can you assess different expressions like:
    is_balanced( [4*circle], [diamond]).
    is_balanced( [diamond], [2*triangle,hexagon]).
    is_balanced([2*square],[3*triangle,circle]).
    etc?
    I’m guessing there should be a way of modeling in Prolog so that the engine can infer that a square is equivalent to a triangle (2nd figure) and that there are many possible ways to balance a diamond…

Not quite sure what kind of answer you’re looking for but maybe it’s something along the following lines.

First, a lot of words to specify the problem I think the diagram is describing: There are 5 kinds of objects, each identified by a colour and a shape. For this specific problem, one of these is redundant, so let’s just use shape. The diagram suggests that each kind has a “weight” property and the problem is to find out what the weights of each kind are. Furthermore the “units” of weight are unspecified (scales only indicate relative weights), so let’s assume that (at least) one of them weighs 1 so the others are some multiple of 1 to permit the scales to balance.

@brebs pretty much defined the clpfd approach to a solution. Step 1 define the variables you want to solve for and the initial domains:

Weights = [CirW,HexW,SqW,TriW,DiaW], Weights ins 1..100,

Step 2: define the 4 constraints as defined by the 4 scales in the diagram:

CirW #= HexW, 2*SqW #= SqW+TriW, SqW #= CirW+HexW, 2*SqW #= DiaW,

Finally, in case the problem isn’t sufficiently constrained at this point, or the constraint propagation isn’t strong enough (e.g., non-linear constraints), perform some kind of labelling/solve step - basically a search. In this case the only thing left to do is to force one of the weights to be 1, so how about

member(1,Weights).

Put them together to produce a solution. In fact it produces two identical solutions (why?).

More properties and constraints? Just add them at the appropriate step. That’s the CLP approach (test then generate), but you should write a standard Prolog version for comparison.

HTH.

P.S. You can try the clpfd solution yourself. Here’s a working query using clpBNR:

?- Weights=[CirW,HexW,SqW,TriW,DiaW], Weights::integer(1,_),
 {CirW == HexW,2*SqW == SqW+TriW,SqW == CirW+HexW,2*SqW == DiaW}, 
 member(1,Weights).

Weights = [1, 1, 2, 2, 4],
CirW = HexW, HexW = 1,
SqW = TriW, TriW = 2,
DiaW = 4 ;
Weights = [1, 1, 2, 2, 4],
CirW = HexW, HexW = 1,
SqW = TriW, TriW = 2,
DiaW = 4 ;
false.

That feels like a bit of a cheat - the relative weights could be such that the smallest relative integer is > 1. So:

?- Weights=[CirW,HexW,SqW,TriW,DiaW], Weights::integer(1,_),
 {CirW == HexW,2*SqW == SqW+TriW,SqW == CirW+HexW,2*SqW == DiaW},
 global_minimum(DiaW, DiaW).
Weights = [1, 1, 2, 2, 4],
CirW = HexW, HexW = 1,
SqW = TriW, TriW = 2,
DiaW = 4.

Well, we need some way to express relative weights, to be able to compare. Given that Prolog has clp (e.g fd and BNR), which have great inferring capability, we can take advantage of their magic to ease our coding - to map e.g. “circle” to a numeric value.

is_balanced then becomes easy maths - e.g. does 2+2=4.

There’s code examples on e.g. stackoverflow, for clpfd and clpBNR.

If that’s the case, the problem is underspecified. Without it, or some similar constraint, there are an infinite number of solutions. You made a similar assumption with ... ins 1..100. (My assumption didn’t specify an upper bound.)

But if you wanted to specify a different minimum, it’s pretty easy:

?- Weights=[CirW,HexW,SqW,TriW,DiaW], MinW=49, Weights::integer(MinW,_),
{CirW == HexW, 2*SqW == SqW+TriW, SqW == CirW+HexW, 2*SqW == DiaW},
member(MinW,Weights).

Weights = [49, 49, 98, 98, 196],
CirW = HexW, HexW = MinW, MinW = 49,
SqW = TriW, TriW = 98,
DiaW = 196 ;
Weights = [49, 49, 98, 98, 196],
CirW = HexW, HexW = MinW, MinW = 49,
SqW = TriW, TriW = 98,
DiaW = 196 ;
false.

Or you could specify a maximum instead and do a more costly search. But none of this is expressed in the diagram expression of the problem.

Just to expand on that, CLP’s are domain specific. clpfd and clpBNR define constraints over numeric domains, so you have to model your program in terms of numbers. If you can formally define your problem in a different domain, you might find a CLP that addresses that.

Isn’t what I used above, more elegant?

global_minimum(DiaW, DiaW).

I guess elegance is in the eye of the beholder, but global_minimum/2 is a pretty heavyweight operation (directed search) to be used in this simple example. But it’s not wrong.

Good! That is exactly what I am looking for,
the kind of proposals from @brebs and @ridgeworks, thank you very much for your contributions.

I can see that it is relatively easy to construct a particular solution for this kind of problems.
However I would like to study some general means to reason symbolically and express it in Prolog.
Can anyone point me to some good study material on this subject?

I think this is far too vague a problem statement to generate a useful response, at least from me. Prolog is a computer language, not a manifestation of some AI.

Perhaps start with a smaller, more concrete and understandable problem to investigate the strengths and weaknesses of logic programming and Prolog technology, and build on that. I thought that’s what you were trying to do with your example, which I think we’ve demonstrated has a fairly straight forward solution in CLP/Prolog.

Can rephrase that as “I would like to become an expert Prolog programmer” :grinning:

Join the club. Prepare to have your mind blown, and to question the nature of reality, and to be (temporarily) stuck at expressing trivial matters sufficiently, repeatedly.

There’s lots of links at Useful Prolog references

Usual recommendation: Power of Prolog videos, because they’re excellent and inspiring.

Here is another take on this, much in the same vein as the solutions by @brebs and @ridgeworks. Though it add one thing: check if other configurations are compatible with those given equations. Here’s a simple model which

  • first define the variables, the equations and solves (game/3) the given balance equations. Note that I added an upper bound (here 10) to the possible value of any of the variables to restrict the number of solutions (using fail/0, see below).
  • then check three different configuration and if they are also satisfied (compatible with the given equations). The third test also calculates the value of X3 (a decision variable), i.e. how many (blue balls * orange diamonds) is needed to balance 1 red ball and 2 yellow boxes.
  • it then use fail to see check for alternative solutions.
:- use_module(library(clpfd)).
go :-
   % Define the variables
    L = [RedBall, BlueBall,YellowBox,GreenTriangle,OrangeDiamond],
        
    % The given equations
    Eqs= [1*RedBall #= 1*BlueBall,
               2*YellowBox #= 1*GreenTriangle + 1*YellowBox,
               1*YellowBox #= 1*RedBall + 1*BlueBall,
               2*YellowBox #= 1*OrangeDiamond],
    
    % Solve the equation system
    MaxVal = 10, % The maximum possible (integer) value for any of the variables
    game(L,MaxVal,Eqs),

    % Print the solution
    writeln([red_ball-RedBall,
             blue_bal-BlueBall,
             yellow_box-YellowBox,
             green_triangle-GreenTriangle,
             orange_diamond-OrangeDiamond]),
    
    % Check some other configuration

    % This is OK
    (12*RedBall #= 12*BlueBall ->
        writeln(ok1)
    ;
        writeln(not_ok1)
    ),

    % This is not OK
    (1*RedBall #= 2*OrangeDiamond ->
        writeln(ok2)
    ;
        writeln(not_ok2)
    ),


    % Figure out the unknown (X3)
    X3 in 0..100,
    (1*RedBall+2*YellowBox #= X3*(BlueBall+OrangeDiamond) ->
        writeln(ok3:X3)
    ;
        writeln(not_ok3)
    ),
    nl,

    % Are there some other possible solutions?
    fail,

    nl.

go.

% Solve the equation system
game(L,MaxVal,Eqs) :-
        L ins 1..MaxVal,
        maplist(call,Eqs),
        label(L).

The output is

[red_ball-1,blue_bal-1,yellow_box-2,green_triangle-2,orange_diamond-4]
ok1
not_ok2
ok3:1

[red_ball-2,blue_bal-2,yellow_box-4,green_triangle-4,orange_diamond-8]
ok1
not_ok2
ok3:1
1 Like

Are we talking simple algebra here or not?

A=B
2C=C+D
C=A+B
2C=E

That looks like what the pictures are telling me. If so, we are looking at ordinary linear algebra. Reduce the equations to close to normal form. Add a new constraint, and use that to reduce further. If reduce fails, contradiction. Else, compatible. CLP(R) will do this behind the scenes, and if the problem is linear algebra, that is the answer. If the problem is integer algebra, CLP(FD) should be able to do.

Anyway, it is arithmetic regardless of A=square or A=5.

1 Like

That is correct. We are dealing with simple algebra for “this family” of problems.
However, I’m not sure if other kind of symbolic reasoning problems will be compatible with numerical reasoning…

I suppose, as @brebs said:
“Can rephrase that as “I would like to become an expert Prolog programmer” :grinning:”

That sounds nice. I am wiling to study in-deep Prolog as a good tool to tackle symbolic reasoning…

The solution by @hakank is very much like what I was looking, thank you!

I am trying to formalize the puzzle as a unification over a commutative monoid M
with the property that the mappling a : x |-> ax (x in M) is an injection for all a in M.
I mean a unifcation that is verly like well-known one by A. Colmerauer. Note that integers are not necessary for finding solved form, bu multi set instead. I think you have done already a similar thing without using integer assignment. But if it’s not the case, I would check through this multiset approach to actual prolog codes without going deep to integer constraint.

@kuniaki.mukai ,

It sounds like you are doing real serious symbolic modeling…
I would really like if you could tell me more about it.
Don’t worry if it is some kind of personal research, I don’t want to steel any secrets or credits,
I just want to comprehend so i can better guide my students…

Not really. Although in general I wish so but I feel I am losing enough energy to do so.
Anyway, my thought is simple as follows, though I am not sure it works as in prolog codes.

Let M(A) =(M, 1) be the free commutative monoid generated by given set A of given shaped objects.

Input P : the puzzle as a set of equations on M(A).
Output S: a solved form of P or “FAIL”
Procedure: Initialize S:=P, then repeat updating S by following steps as far as possible, where X, Y, U, V, A \in M(A).
Property: The procedure always terminates. If the output is FAIL then there is no positive integer assignment for the input equations, otherwise the set of positive integer assignments for the output S is the same as for the
input P.

  1. Remove X=X from S.

  2. 1=X \in S \land X\ne 1 \Rightarrow \mbox{FAIL}.

  3. XAY=UAV \Rightarrow XY=UV

  4. 1X=X1=X

  5. AX=Y \land AU=V \Rightarrow XV=YU (A does not appear in X, Y, U, V) (Confrontation)

  6. X = a \Rightarrow a= X (Contraposition)

  7. a = X \in S then rewrite S to rewrite

S:=\{\theta(X/a, L)=\theta(X/a, R) \mid L=R \in S\}\setminus \{a=X\},

where \theta(X/a, P) is the substitution of P by a with X (Variable Elimination).

I only hope that the above solver is a minor variant of A. Colemearuers unification theory on rational trees.

By the way, the picture in your post was impressive reminding me of some visual inference sytem, thinking of adding inequlity (unballanced cases) to the puzzle.