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:
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])
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?
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: