How to generate distinct solutions in Prolog for '8 out of 10 cats does countdown' numbers game solver?

Question

I wrote a Prolog program to find all solutions to any '8 out of 10 cats does countdown' number sequence. I am happy with the result. However, the solutions are not unique. I tried distincts() and reduced() from the "solution sequences" library. They did not produce unique solutions.

The problem is simple. you have a given list of six numbers [n1,n2,n3,n4,n5,n6] and a target number (R). Calculate R from any arbitrary combination of n1 to n6 using only +,-,*,/. You do not have to use all numbers but you can only use each number once. If two solutions are identical, only one must be generated and the other discarded. 

Sometimes there are equivalent results with different arrangement. Such as:

(100+3)*6*75/50+25
(100+3)*75*6/50+25  

Does anyone has any suggestions to eliminate such redundancy?

Each solution is a nested operators and integers. For example +(2,*(4,-(10,5))). This solution is an unbalanced binary tree with Arithmetic Operator for root and sibling nodes and numbers for leaf nodes. In order to have unique solutions, no two trees should be equivalent.

The Code:

:- use_module(library(lists)).
:- use_module(library(solution_sequences)).

solve(L,R,OP) :-
    findnsols(10,OP,solve_(L,R,OP),S),
    print_solutions(S).

solve_(L,R,OP) :-
    distinct(find_op(L,OP)),
    R =:= OP.

find_op(L,OP) :-
    select(N1,L,Ln),
    select(N2,Ln,[]),
    N1 > N2,
    member(OP,[+(N1,N2), -(N1,N2), *(N1,N2), /(N1,N2), N1, N2]).
find_op(L,OP) :-
    select(N,L,Ln),
    find_op(Ln,OP_),
    OP_ > N,
    member(OP,[+(OP_,N), -(OP_,N), *(OP_,N), /(OP_,N), OP_]).

print_solutions([]).
print_solutions([A|B]) :-
  format('~w~n',A),
  print_solutions(B).

Test:

solve([25,50,75,100,6,3],952,X)

Result

(100+3)*6*75/50+25 <- s1
((100+6)*3*75-50)/25 <- s2
(100+3)*75*6/50+25 <- s1
((100+6)*75*3-50)/25 <- s2
(100+3)*75/50*6+25 <- s1
true.

• This code uses select/3 from the "lists" library.

UPDATE: Generate solutions useing DCG

The following is an attempt to generate solutions using DCG.  I was able to generate a more exhaustive solution set than in previous code posted. In a way, using DCG resulted in a more correct and elegant code. However, it is much more difficult to 'guess' what the code is doing.

The issue of redundant solutions still persist.

:- use_module(library(lists)).
:- use_module(library(solution_sequences)).

s(L) --> [L].

s(+(L,Ls)) --> [L],s(Ls).
s(*(L,Ls)) --> [L],s(Ls), {L =\= 1, Ls =\= 1, Ls =\= 0}.

s(-(L,Ls)) --> [L],s(Ls), {L =\= Ls, Ls =\= 0}.
s(/(L,Ls)) --> [L],s(Ls), {Ls =\= 1, Ls =\= 0}.

s(-(Ls,L)) --> [L],s(Ls), {L =\= Ls}.
s(/(Ls,L)) --> [L],s(Ls), {L =\= 1, Ls =\=0}.

solution_list([N,H|[]],S) :-
    phrase(s(S),[N,H]).

solution_list([N,H|T],S) :-
    phrase(s(S),[N,H|T]);
    solution_list([H|T],S).

solve(L,R,S) :-
    permutation(L,X),
    solution_list(X,S),
    R =:= S.

Answer 1

Does anyone has any suggestions to eliminate such redundancy?

I suggest to define a sorting weight on each node (inner or leaf). The number resulting from reducing the child node could be used, although ties will appear. These can be broken by additionally looking at topmost operations, sorting * before + for example. Actually one would like to have a sorting operation for which "tie" means "exactly the same subtree of arithmetic operations".

Answer 2

Since the OP is only seeking hints to help solve the problem.

1. Use DCG as a generator. (SWI-Prolog) (Prolog DCG Primer)
   a. For a more refined version of using DCGs as a generator look for examples that use length/2. When you understand why you might see a beam of light shining down on you for a few moments (The light beam is a video gaming thing).
2. Use a constraint solver (SWI-Prolog) (CLP(FD) and CLP(?): Prolog Integer Arithmetic) (Understanding CLP(FD) Prolog code of N-queens problem)
3. Since your solutions are constrained to the 6 numbers and the operators are always binary operators (+,-,*,/) then it is possible to enumerate the unique binary trees. If you know about OEIS then you can find related links that can help you solve this problem, but you need to give OEIS a sequence. To get a sequence for use with OEIS draw the trees for N from 2 to 5 and then enter that sequence into OEIS and see what you get. e.g.

N is the number of leaf (*) nodes.

N=2  ( 1 way to draw the tree )
   -  
  / \  
 *   *  

N=3  ( 2 ways to draw the tree )
     -       -  
    / \     / \  
   -   *   *   -  
  / \         / \  
 *   *       *   *  

So the sequence starts with 1,2 ...

Hint - This page (link died) shows the images of the trees to see if you have done it correctly. In the description I use N to count the number of leaves (*), but on this page they use N to count the number of internal nodes (-). If we call my N N1 and the page N N2, then the relation is N2 = N1 - 1

4. This might be a Hamiltonian Cycle (Wolfram World) (Hamiltonianicity of the Tower of Hanoi Problem) Remember that there is a relation between Binary Trees and the Tower of Hanoi, but in your case there are added constraints. I don't know if the constraints eliminate a solution as a Hamiltonian Cycle.

Also don't think of building the final answer from a combination of any number and operator, but instead build subsets of operators and numbers, and then use those subsets to build the answer. You constrain at the start, not at the end.

Or put another way, don't think combinations at the start, but permutations of combinations (not sure if that is the correct pattern, but in the ball park) and then using that build the tree.