Mister X

Although this problem has a straightforward solution, it does demonstrate the value of thinking declaratively in understanding the problem, which relates to "don't know" nondeterminism, and an appropriate use of "lemmas".

Problem:

Problem as posted to comp.lang.prolog by Thorsten Seelend. Also known as Hans Freudenthal's Impossible Puzzle.

Mister X thinks about two integers between 1 and 100 excluding:

MISTERX: Two integers, X and Y between 2 and 99 (My formalization of the given information)

<syntaxhighlight lang="prolog">two_integers( X, Y ) :-

   between( 2, 98, X ),
   between( X, 99, Y ).</syntaxhighlight>

He tells Susan the Sum of them and Peter their Product. Their task is to get the two original values without telling each other the numbers that Mister X told them.

After some time Peter says: "I can't say definitively which are the original numbers."

PETER1: There is more than one pair of factors giving Product

<syntaxhighlight lang="prolog">property( peter1, Product ) :-

   \+ unique_factors( Product ).</syntaxhighlight>

Then Susan responds:

"Neither can I, but I knew that you couldn't know it."

SUSAN1: The product of every pair of summands giving Sum has the property PETER1

<syntaxhighlight lang="prolog">property( susan1, Sum ) :-

   forall( ordered_summands(Sum, X, Y), peter1(X * Y) ).</syntaxhighlight>

Peter: "Really? So now I know the original numbers".

PETER2: exactly one pair of factors giving Product gives a sum with the property SUSAN1

<syntaxhighlight lang="prolog">property( peter2, Product ) :-

   unique_solution( (ordered_factors(Product, X, Y), susan1(X+Y)) ).</syntaxhighlight>

Susan: "Now I know them too".

SUSAN2: exactly one pair of summands giving Sum has a product with the property PETER2

<syntaxhighlight lang="prolog">property( susan2, Sum ) :-

   unique_solution( (ordered_summands(Sum, X, Y), peter2(X * Y)) ).</syntaxhighlight>

Question: What are the two numbers that Mister X thought of?

Unique solution

<syntaxhighlight lang="prolog">solve( X, Y ) :-

   unique_solution( mister_x(X, Y) ).

mister_x( X, Y ) :-

   two_integers( X, Y ),
   Sum is X + Y,
   Product is X * Y,
   peter1( Product ),
   susan1( Sum ),
   peter2( Product ),
   susan2( Sum ).</syntaxhighlight>

Macros

<syntaxhighlight lang="prolog">peter1( Product ) :-

   lemma( peter1, Product ).

peter2( Product ) :-

   lemma( peter2, Product ).

susan1( Sum ) :-

   lemma( susan1, Sum ).

susan2( Sum ) :-

   lemma( susan2, Sum ).</syntaxhighlight>

Lemmas

lemma( +Property, +Expression )

holds wherever Property holds for Expression.

Asserted facts are used to record successful (positive) or failed (negative) demonstrations. This saves recomputation without changing the meaning of the pure program.

Although the use of side-effects is generally undesirable, the use of lemmas is justified when the alternative is to compromise performance or clarity.

Using lemmas or tabling to cache results is an order of magnitude faster than recalculating each property every time it is used. <syntaxhighlight lang="prolog">:- dynamic positive/2, negative/2.

lemma( Name, Expression ) :-

   Value is Expression,
   ( positive( Value, Name ) ->
       true
   ; \+ negative( Value, Name ) ->
       ( property(Name, Value) ->
          assert( positive(Value, Name) )
       ; otherwise ->
          assert( negative(Value, Name) ),
          fail
       )
   ).</syntaxhighlight>

Supporting Predicates

ordered_summands( +Sum, ?X, ?Y )

when X ≤ Y and Sum = X+Y. NB: Since X≤Y it follows that X ≤ Sum/2. <syntaxhighlight lang="prolog">ordered_summands( Z, X, Y ) :-

   Half is Z//2,
   between( 2, Half, X ),
   Y is Z - X,
   between( X, 98, Y ).</syntaxhighlight>

ordered_factors( +Product, ?X, ?Y )

when X ≤ Y and Product = X × Y. NB: Since X≤Y it follows that X ≤ √Product. <syntaxhighlight lang="prolog">ordered_factors( Z, X, Y ) :-

   integer_sqrt( Z, SqrtZ ),
   between( 2, SqrtZ, X ),
   Y is Z // X,
   between( X, 99, Y ),
   Z =:= X * Y.</syntaxhighlight>

unique_factors( +Product )

when Product has exactly one pair of factors. <syntaxhighlight lang="prolog">unique_factors( Product ) :-

   ordered_factors( Product, X, _Y ),
   \+ (ordered_factors(Product, X1, _Y1), X1 =\= X).</syntaxhighlight>

integer_sqrt( +N, ?Sqrt )

when Sqrt² ≤ N and (Sqrt+1)² ≥ N. <syntaxhighlight lang="prolog">integer_sqrt( N, Sqrt ) :-

   Float is N * 1.0,
   sqrt( Float, FSqrt ),
   Sqrt is integer(FSqrt).</syntaxhighlight>

Load a small library of Puzzle Utilities.

<syntaxhighlight lang="prolog">

- ensure_loaded( misc ).

</syntaxhighlight> The code is available as plain text here.

Result

This program finds X and Y as 4 and 13.

Tabling

Using tabling, rather than explicit lemmas, can simplify code. A version adapted for XSB Prolog is available here.