Hard Prolog Problem - Permutation of Equations

[dejaWCD]

I have a very hard problem (well for me anyway), and i need help!
Given a list of integers (positive integeres only), the program inserts one equality sign and arithmetic operators between the numbers so that ALL valid equations are obtained. The order of the integers in the list have to be maintained. For example the query equate([1,2,3,4,5])? outputs:

1 = 2 / (3 + (4 - 5))
1 = 2 / (3 + 4 - 5 )
1 = 2 - 3 * (4 - 5)
1 = (2 - 3) / (4 - 5)
1 = (2 - 3) * 4 + 5
1 * 2 = 3 + (4 - 5)
1 * 2 = 3 + 4 - 5
1 * (2 - 3) = 4 - 5
1 / (2 - 3) = 4 - 5
(1 + 2) * 3 = 4 + 5
1 * 2 - 3 = 4 - 5
1 - (2 - 3) * 4 = 5
(1 + 2) * 3 - 4 = 5
(1 + 2) / 3 + 4 = 5
**yes

Basically if the = is replaced by a =:= then the answer to the corressponding equation being tested should be yes, no other rules apply.

I welcome anyone who could help me with this problem in any way!

 

[pimi]

Hello.
This is an incomplete program.
Please change post-fix notation to in-fix notation.

%%% solve([3, 2, 1], Ans) ->
%%% [3] = [2, 1, +];
%%% [3, 2, -] = [1].

solve(N, Ans) :-
split(N, L, R),
pattern(L, 0, [], LPattern),
pattern(R, 0, [], RPattern),
calc(LPattern, [], LAns),
calc(RPattern, [], RAns),
LAns =:= RAns,
write(LPattern),
write(' = '),
write(RPattern),
nl,
fail.

%%% op(Op) ->
%%% Op = +;
%%% Op = -;
%%% Op = *;
%%% Op = /.

op('+').
op('-').
op('*').
op('/').

%%% calc2('-', 7, 4, Ans) ->
%%% Ans = 3.

calc2('+', N1, N2, N3) :- N3 is N1 + N2.
calc2('-', N1, N2, N3) :- N3 is N1 - N2.
calc2('*', N1, N2, N3) :- N3 is N1 * N2.
calc2('/', N1, N2, N3) :- N2 =\= 0, N3 is N1 / N2.

%%% calc([3, 2, +, 4, *], [], Ans) ->
%%% Ans = 20.

calc([], [Ans], Ans).

calc([N1|Ns], Work, Ans) :-
number(N1),
calc(Ns, [N1|Work], Ans).

calc([N1|Ns], [W1, W2|Ws], Ans) :-
op(N1),
calc2(N1, W2, W1, W3),
calc(Ns, [W3|Ws], Ans).

%%% cat([a, b], [c, d, e], Ans) ->
%%% Ans = [a, b, c, d, e].

cat([], R, R).
cat([L1|Ls], R, [L1|Work]) :- cat(Ls, R, Work).

%%% split([a, b, c], L, R) ->
%%% L = [a], R = [b, c];
%%% L = [a, b], R = [c].

split(N, L, R) :-
cat(L, R, N),
L \== [],
R \== [].

%%% pattern([1, 2], 0, [], Ans) ->
%%% Ans = [1, 2, +];
%%% Ans = [1, 2, -];
%%% Ans = [1, 2, *];
%%% Ans = [1, 2, /].

pattern([], 1, Ans, Ans).

pattern([N1|Ns], Depth, Work, Ans) :-
DepthNext is Depth + 1,
cat(Work, [N1], WorkNext),
pattern(Ns, DepthNext, WorkNext, Ans).

pattern(N, Depth, Work, Ans) :-
Depth >= 2,
DepthNext is Depth - 1,
op(Op),
cat(Work, [Op], WorkNext),
pattern(N, DepthNext, WorkNext, Ans).

********************************

sample:

?- solve([1, 2, 3, 4, 5], Ans).
[1] = [2,3,4,5,-,+,/]
[1] = [2,3,4,+,5,-,/]
[1] = [2,3,-,4,5,-,*]
[1] = [2,3,-,4,5,-,/]
[1] = [2,3,-,4,*,5,+]
[1,2,*] = [3,4,5,-,+]
[1,2,*] = [3,4,+,5,-]
[1,2,3,-,*] = [4,5,-]
[1,2,3,-,/] = [4,5,-]
[1,2,+,3,*] = [4,5,+]
[1,2,*,3,-] = [4,5,-]
[1,2,3,-,4,*,-] = [5]
[1,2,+,3,*,4,-] = [5]
[1,2,+,3,/,4,+] = [5]
no

?- solve([5, 4, 3, 2, 1], Ans).
[5] = [4,3,2,1,+,/,+]
[5] = [4,3,2,1,*,-,+]
[5] = [4,3,2,1,/,-,+]
[5] = [4,3,2,-,1,*,+]
[5] = [4,3,2,-,1,/,+]
[5] = [4,3,2,-,+,1,*]
[5] = [4,3,2,-,+,1,/]
[5] = [4,3,2,-,*,1,+]
[5] = [4,3,2,-,/,1,+]
[5] = [4,3,2,/,*,1,-]
[5] = [4,3,+,2,1,*,-]
[5] = [4,3,+,2,1,/,-]
[5] = [4,3,+,2,-,1,*]
[5] = [4,3,+,2,-,1,/]
[5] = [4,3,*,2,/,1,-]
[5,4,+] = [3,2,1,+,*]
[5,4,-] = [3,2,1,+,/]
[5,4,-] = [3,2,1,*,-]
[5,4,-] = [3,2,1,/,-]
[5,4,-] = [3,2,-,1,*]
[5,4,-] = [3,2,-,1,/]
[5,4,+,3,/] = [2,1,+]
[5,4,-,3,*] = [2,1,+]
[5,4,3,2,-,+,/] = [1]
[5,4,3,2,-,*,-] = [1]
[5,4,3,2,-,/,-] = [1]
[5,4,3,+,2,-,/] = [1]
[5,4,+,3,/,2,-] = [1]
[5,4,-,3,2,-,*] = [1]
[5,4,-,3,2,-,/] = [1]
[5,4,-,3,*,2,-] = [1]
no