[colanderman]

You can do this without the intermediate step of generating all permutations simply like so:

    order([]).
    order([_]).
    order([X,Y|L]) :-
        follows(Y, X), order([Y|L]).

    ?- length(L, 9), order(L).
    L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .

This is likely more efficient as we're cutting short the generation of most permutations.

Or you can use CPL(FD) as suggested by @Avshalom below, though more heavyweight this is likely more efficient still.

The most efficient though is simply to use a topological sort algorithm, which will run in linear time, unlike any of these solutions (some of which are exponential). SWI Prolog has this built-in:

    ?- findall(X-Y, is_behind(Y, X), Edges), vertices_edges_to_ugraph([], Edges, UG), top_sort(UG, L).
    L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer].

[tannhaeuser]

Putting OP's and your clauses together, I get the following pure ISO Prolog program and query that you can paste directly into Quantum Prolog's in-browser execution console at https://quantumprolog.sgml.io/browser-demo/browser-demo.html for execution in no time:

    % Vixen should be behind Rudolph,
    % Prancer and Dasher,
    is_behind(vixen, rudolph).
    is_behind(vixen, prancer).
    is_behind(vixen, dasher).

    % whilst Vixen should be in front
    % of Dancer and Comet.
    is_behind(dancer, vixen).
    is_behind(comet, vixen).

    % Dancer should be behind Donder,
    % Blitzen and Rudolph.
    is_behind(dancer, donder).
    is_behind(dancer, blitzen).
    is_behind(dancer, rudolph).

    % Comet should be behind Cupid,
    % Prancer and Rudolph.
    is_behind(comet, cupid).
    is_behind(comet, prancer).
    is_behind(comet, rudolph).

    % Donder should be behind Comet,
    % Vixen, Dasher, Prancer and
    % Cupid.
    is_behind(donder, comet).
    is_behind(fonder, vixen).
    is_behind(donder, dasher).
    is_behind(donder, prancer).
    is_behind(donder, cupid).

    % Cupid should be in front of
    % Comet, Blitzen, Vixen, Dancer
    % and Rudolph.
    is_behind(comet, cupid).
    is_behind(blitzen, cupid).
    is_behind(vixen, cupid).
    is_behind(dancer, cupid).
    is_behind(rudolph, cupid).

    % Prancer should be in front of
    % Blitzen, Donder and Cupid.
    is_behind(blitzen, prancer).
    is_behind(donder, prancer).
    is_behind(cupid, prancer).

    % Blitzen should be behind Cupid
    % but in front of Dancer, Vixen
    % and Donder.
    is_behind(blitzen, cupid).
    is_behind(dancer, blitzen).
    is_behind(vixen, blitzen).
    is_behind(donder, blitzen).

    % Rudolph should be behind Prancer
    % but in front of Dasher, Dancer
    % and Donder.
    is_behind(rudolph, prancer).
    is_behind(dasher, rudolph).
    is_behind(dancer, rudolph).
    is_behind(donder, rudolph).

    % Finally, Dasher should be behind
    % Prancer but in front of Blitzen,
    % Dancer and Vixen.
    is_behind(dasher, prancer).
    is_behind(blitzen, dasher).
    is_behind(dancer, dasher).
    is_behind(vixen, dasher).

    follows(Last, First) :-
      is_behind(Last, First).
    follows(Last, First) :-
      is_behind(Middle, First),
      follows(Last, Middle).

    order([]).
    order([_]).
    order([X,Y|L]) :-
        follows(Y, X), order([Y|L]).

    ?- order([A,B,C,D,E,F,G,H,I])

[_xgw]

Ah, interesting! I figured there would be a way without having to "brute-force" the solution by using the `permutation` predicate but I wasn't able to come up with one. I wonder if there's a way of not depending on permutation generation, nor list length. Does querying with `order(L)` require `length(L, 9)` to work?

As for the topological sort solution, I assume it's what Graphviz uses under the hood in mLuby's solution! If I understand correctly, we're graphing the sequence of reindeer and then extracting the order of the nodes in the graph?

[colanderman]

No, `order/1` generates "too-short" solutions otherwise. If you redefine `order/1` to be a little smarter, like so:

    order([]) :- \+ follows(_, _).
    order([X]) :- \+ follows(_, X).
    order([X,Y|L]) :-
        follows(Y, X), order([Y|L]).

Then this works without knowing the length a priori, but it's less efficient:

    ?- order(L), forall((is_behind(X, _); is_behind(_, X)), member(X, L)).
    L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .

Instead I'd discover the set of names (and therefore list length) using `setof/3`; this is similarly efficient to my original solution:

    ?- setof(X, Y^(is_behind(X, Y); is_behind(Y, X)), M), length(M, N), length(L, N), order(L).
    M = [blitzen, comet, cupid, dancer, dasher, donder, prancer, rudolph, vixen],
    N = 9,
    L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .