Professor Klinger stopped by my office the other day and gave me a puzzle to solve: generate the number 24 given only three 5s, a single 1, and +, -, *, and /. I cheated and generated the solution 5*5 - 1**5, but he has since clarified the puzzle by saying that the four operators are the usual binary arithmetic operators, and that one cannot cheat by using exponentiation or concatenation. You might try doing the problem by hand first, before looking at Professor Klinger's animated solution.
Rather than spend more time solving the problem, I thought I'd have you solve it for me by writing a solver for a more general class of problems. This of course is the usual strategy in academia: get your students to do the grunt work!
Write a Prolog predicate kpuzzle/3 that takes three arguments: a list of numbers L, an arithmetic expression E, and a number X, and succeeds if E is an expression that contains exactly the numbers in L and that evaluates to X. E may contain any of the binary operators mentioned above. E may not contain an error (e.g., division by zero), because such an expression does not evaluate to any value; however, E may contain overflows (e.g., 268435455 + 1) since the resulting behavior is well-defined in GNU Prolog.
Your implementation may assume that L is a ground term, but it should not make that assumption for E or X, and should backtrack through all possible solutions if requested.
To turn in your assignment, submit a file kpuzzle.prolog containing your definition of kpuzzle, and any other auxiliary definitions. The first line of kpuzzle.prolog should be a comment containing your name and student ID.
Your solution should be free of side effects: for example, it should not use assert/1 or retract/1. However, it may use cuts.
You need not worry about filtering out identical solutions. For example, kpuzzle([1,1], E, V) should generate E = 1+1 twice (though it should not generate that solution more than twice).
Also submit a brief ASCII text file kpuzzle.txt explaining two things.:
Make sure that your code works with the GNU Prolog installation on SEASnet.
In these examples, the programmer repeatedly typed ";" in order to backtrack through all possible solutions. Your program need not generate solutions in the same order as this transcript, but it should generate the same solutions overall. Your program's final response need not agree with the yes and ; no responses in the examples shown below; for example, it can output yes where the example below waits for the user to type ; before it outputs no.
> gprolog
GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- ['kpuzzle.prolog'].
compiling …/kpuzzle.prolog for byte code...
…
yes
| ?- kpuzzle([], E, V).
no
| ?- kpuzzle([100], E, V).
E = 100
V = 100 ? ;
no
| ?- kpuzzle([5,10], E, V).
E = 10+5
V = 15 ? ;
E = 10-5
V = 5 ? ;
E = 10*5
V = 50 ? ;
E = 10/5
V = 2.0 ? ;
E = 5+10
V = 15 ? ;
E = 5-10
V = -5 ? ;
E = 5*10
V = 50 ? ;
E = 5/10
V = 0.5 ? ;
no
| ?- kpuzzle([0,0], E, V).
E = 0+0
V = 0 ? ;
E = 0-0
V = 0 ? ;
E = 0*0
V = 0 ? ;
E = 0+0
V = 0 ? ;
E = 0-0
V = 0 ? ;
E = 0*0
V = 0 ? ;
no
| ?- setof(V=E, (kpuzzle([5,5,5,1], E, V), 23<V, V<25), L).
L = [24.0=5*(5-1/5),24.0=(5-1/5)*5,24.800000000000001=5*5-1/5]
(Note that order is not important in the above list.)
yes
| ?- findall(V0-E, (kpuzzle([5,5,5,1], E, V), V0 is float(V)), L),
sort(L, SL),
keysort(SL, KSL),
member(X, KSL), write(X), nl, fail.
-124.0-(1-5*(5*5))
-124.0-(1-5*5*5)
-120.0-5*(1-5*5)
-120.0-(1-5*5)*5
-100.0-5*(5*(1-5))
-100.0-5*((1-5)*5)
-100.0-5*5*(1-5)
-100.0-5*(1-5)*5
-100.0-(1-5)*5*5
-100.0-(1-5)*(5*5)
…
130.0-5*(1+5*5)
130.0-5*(5*5+1)
130.0-(1+5*5)*5
130.0-(5*5+1)*5
150.0-5*(5*(1+5))
150.0-5*(5*(5+1))
150.0-5*((1+5)*5)
150.0-5*((5+1)*5)
150.0-5*5*(1+5)
150.0-5*5*(5+1)
150.0-5*(1+5)*5
150.0-5*(5+1)*5
150.0-(1+5)*5*5
150.0-(5+1)*5*5
150.0-(1+5)*(5*5)
150.0-(5+1)*(5*5)