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

Answers vs. solutions

From your question it is not clear what you mean by "unique solutions". After all, you say:

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

Consider the goal (X = 1, repeat). The total number of unique solutions is one. But still, you will not be able to stop, since you do not know whether or not you found all solutions. So if N is greater than 1, you have to loop. Or consider ( repeat, between(1,10,N) ) here there are ten unique solutions, so if N is below or equal 10 you can find them all, and terminate.

Please note that Prolog produces answers that may contain solutions. Typically, you get an answer substitution that is not necessarily ground. Think of X = t(_). This answer contains infinitely many solutions, like X = t(1), X = t(2) etc.

Most probably you wanted to see the first N answers. A solution to that is here.

Taking your question literally (that is: always terminating goal, ground answers), simply wrap setof(t,Goal,_) around the goal.

Answer 3

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)).