Finding up to N unique solutions of a goal in Prolog

Question

Could you tell me how to find up to N unique solutions of a goal in Prolog?

I know using findall/3 all the solutions of a goal can be found, but for a goal which has too many, or infinite solutions, I want to find only up to N unique solutions if it is enough.

What I want to do is like this:

?- find_unique_n(10, X, any_goal(X), Xs).
Xs = [...] % up to 10 unique solutions.

If the total number of the unique solutions for a goal is below N, I want to find all of them.

Edit: As false pointed out, itt was not clear what 'unique solutions' means. If sample_goal/1 is defined as below:

sample_goal(1).
sample_goal(1).
sample_goal(2).
sample_goal(2).

the expected results are:

?- find_unique_n(1, X, sample_goal(X), Xs).
Xs = [1]
?- find_unique_n(2, X, sample_goal(X), Xs).
Xs = [1,2]
?- find_unique_n(3, X, sample_goal(X), Xs).
Xs = [1,2]

And for goals with infinite solutions, the expected results are:

?- find_unique_n(2, X, (repeat, between(1,2,X)), Xs).
Xs = [1,2]
?- find_unique_n(3, X, (repeat, between(1,2,X)), Xs).
% This won't stop, it's ok

Answer 1

Here is a solution, although not particularly efficient. The idea is to repeatedly call (copies of) Goal, looking for solutions that are not yet in the Sols list:

find_unique_n(N, X, Goal, Xs) :-
    find_unique_n(N, X, Goal, Xs, []).

find_unique_n(N, X, Goal, Xs, Sols) :-
    N > 0,
    copy_term(X-Goal, CX-CGoal),
    call(CGoal),
    \+ (member(Sol,Sols), variant(Sol,CX)),
    !,
    N1 is N-1,
    Xs = [CX|Xs1],
    Sols1 = [CX|Sols],
    find_unique_n(N1, X, Goal, Xs1, Sols1).
find_unique_n(_N, _X, _Goal, [], _Sols).

If your solutions are all ground, you can use ==/2 in place of variant/2.

Alternatively, if your Prolog has convenient primitives to save data across backtracking, you can use a failure-driven approach like in the following ECLiPSe example:

find_unique_n(N, X, Goal, Xs) :-
    store_create(Solutions),
    (
        once((
            call(Goal),
            store_set(Solutions, X, _),
            store_count(Solutions) >= N
        )),
        fail
    ;
        stored_keys(Solutions, Xs)
    ).

where the store-primitives implement a non-backtrackable hash table. Similar solutions using assert/retract are possible, but nontrival to make reentrant and memory leak free.

Answer 2

After your clarifications, this is a very compact solution, that contains also some reusable predicates, see this answer for call_firstn/2 and the other predicates.

find_unique_n(N, X, Goal_0, Xs) :-
   findall(X, call_firstn(call_nub(Goal_0), N), Xs).

So the nub is call_nub/1 below. Nub, as in nub.

Caveat: This version requires setup_call_cleanup/3 or call_cleanup/2 to work properly and it does not work together with constraints.

:- dynamic(nub_answer_id/2).
:- dynamic(generated_id/1).

:- meta_predicate(call_nub(0)). % only for SICStus/SWI/YAP
call_nub(Goal_0) :-
   setup_call_cleanup(
      genid(Id),
      (  term_to_vec(Goal_0, Vec),
         Goal_0,
         (  \+nub_answer_id(Vec, Id)
         -> true
         ;  \+ ( nub_answer_id(XVec, Id), subsumes_term(XVec, Vec) )
         ),
         asserta(nub_answer_id(Vec, Id))
      ),
      retractall(nub_answer_id(_,Id))
   ).

term_to_vec(T, Vec) :-
   term_variables(T, Vs),
   catch(Vec=..[v|Vs],error(representation_error(max_arity),_),T=Vec).

genid(Id) :-
   (  generated_id(Id0) -> true ; Id0 = 0 ),
   Id1 is Id0 + 1,
   asserta(generated_id(Id1)),
   retractall(generated_id(Id0)),
   Id1 = Id.

setup_call_cleanup(Setup_0, Call_0, Cleanup_0) :- % only for SICStus
   once(Setup_0),
   call_cleanup(Call_0, once(Cleanup_0)).