Prolog, remove repetitive results in generation

I wrote a prolog program which generates all possible positions of elements in a two-dimensional table. The number of elements and the table size are given.

My code is:

geni(Min, Min, Max) :- Min =< Max.
geni(Min, X, Max) :- Max >= Min, 开发者_JS百科MinInc is Min+1, geni(MinInc, X, Max).
generate(_, 0, []) :- !.
generate(TSize, N, [X|Tail]) :- NDec is N-1, generate(TSize,NDec, Tail),
                                X=k(X1,Y1), geni(1,X1,TSize), geni(1,Y1,TSize), 
                                not(member(X, Tail)).

(there TSize is the size of table, N is the number of elements, and the last one is the result) Predicate geni generates number X in interval [A;B].

Example (2 elements in 2x2 table):

?- generate(2, 2, R).
R = [k(1, 1), k(1, 2)] ;
R = [k(1, 1), k(2, 1)] ;
R = [k(1, 1), k(2, 2)] ;
R = [k(1, 2), k(1, 1)] ;
R = [k(1, 2), k(2, 1)] ;
R = [k(1, 2), k(2, 2)] ;
R = [k(2, 1), k(1, 1)] ;
R = [k(2, 1), k(1, 2)] ;
R = [k(2, 1), k(2, 2)] ;
R = [k(2, 2), k(1, 1)] ;
R = [k(2, 2), k(1, 2)] ;
R = [k(2, 2), k(2, 1)] ;
false.

My table is chess board and elements are knights. In this case all elements are equal but my program "think" that the are different. How to avoid equal results? Like this:

R = [k(1, 1), k(1, 2)] ;
R = [k(1, 2), k(1, 1)] ;

Currently, you are using not(member(...)) to ensure the result contains no duplicate. To avoid getting all permutations of a result, you just have to make sure the elements in the result are ordered.

Step 1 is to define an order, i.e. like this:

% A knight 1 is "bigger" than knight 2
% if the X-value is bigger or X is equal and Y is bigger
is_bigger(k(X1, Y1), k(X2, Y2)) :-
    X1 > X2; (X1 = X2, Y1 > Y2).

Now you have to ensure that the element you want to add to the list is "bigger" than all other elements.

geni(Min, X, Max) :- between(Min, Max, X).
generate(_, 0, []) :- !.
generate(TSize, N, [X|Tail]) :- X=k(X1,Y1),  NDec is N-1,
                            generate(TSize,NDec, Tail),
                            geni(1,X1,TSize),
                            geni(1,Y1,TSize),
                            maplist(is_bigger(X), Tail).

I am using the build-in predicate maplist to test all elements of the list. Frome the example it should be clear how it works.

If you want to reverse the order, implement a "lower" instead.

?- generate(2, 2, T).
T = [k(1, 2), k(1, 1)] ;
T = [k(2, 1), k(1, 1)] ;
T = [k(2, 2), k(1, 1)] ;
T = [k(2, 1), k(1, 2)] ;
T = [k(2, 2), k(1, 2)] ;
T = [k(2, 2), k(2, 1)] ;
false.