Prolog was made to parse text, so shouldn't we derive the constraints from the text itself with a DCG ?

:- set_prolog_flag(double_quotes, codes).

text("Vixen should be behind Rudolph, Prancer and Dasher, whilst Vixen should be in front of Dancer and Comet. Dancer should be behind Donder, Blitzen and Rudolph. Comet should be behind Cupid, Prancer and Rudolph. Donder should be behind Comet, Vixen, Dasher, Prancer and Cupid. Cupid should be in front of Comet, Blitzen, Vixen, Dancer and Rudolph. Prancer should be in front of Blitzen, Donder and Cupid. Blitzen should be behind Cupid but in front of Dancer, Vixen and Donder. Rudolph should be behind Prancer but in front of Dasher, Dancer and Donder. Finally, Dasher should be behind Prancer but in front of Blitzen, Dancer and Vixen.").

space -->
" ".

reindeer('Blitzen') -->
"Blitzen".
reindeer('Comet') -->
"Comet".
reindeer('Cupid') -->
"Cupid".
reindeer('Dancer') -->
"Dancer".
reindeer('Dasher') -->
"Dasher".
reindeer('Donder') -->
"Donder".
reindeer('Prancer') -->
"Prancer".
reindeer('Rudolph') -->
"Rudolph".
reindeer('Vixen') -->
"Vixen".

complement(S, P, [[S, P, Reindeer] | R], R) -->
reindeer(Reindeer).

sep -->
", ".
sep -->
" and ".

list(Pred, Sep, S1, S3) -->
call(Pred, S1, S2),
list_next(Pred, Sep, S2, S3).
list_next(Pred, Sep, S1, S3) -->
Sep,
call(Pred, S1, S2),
list_next(Pred, Sep, S2, S3).
list_next(_, _, S, S) -->
[].

position(>) -->
"behind".
position(<) -->
"in front of".

text(S) -->
list(proposition, space, S, S2),
space,
last_sentence(S2, []).

last_sentence(S1, S2) -->
"Finally, ",
proposition(S1, S2).

proposition(S1, S3) -->
proposition(R, S1, S2),
inverse_proposition(R, S2, S3),
".".

proposition(R, S1, S2) -->
reindeer(R),
" should be ",
position_list(R, S1, S2).

position_list(R, S1, S2) -->
position(P),
space,
list(complement(R, P), sep, S1, S2).

inverse_proposition(R, S1, S2) -->
" but ",
position_list(R, S1, S2).
inverse_proposition(R, S1, S2) -->
", whilst ",
proposition(R, S1, S2).
inverse_proposition(_, S, S) -->
[].

:- table(follows/3).

follows(R1, R2, Pairs) :-
member([R1, >, R2], Pairs).
follows(R1, R2, Pairs) :-
member([R2, <, R1], Pairs).
follows(R1, R3, Pairs) :-
follows(R1, R2, Pairs),
follows(R2, R3, Pairs).

order([X | L], Pairs) :-
order(L, X, Pairs).

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

And we can solve the riddle with:

?- text(T), phrase(text(Pairs), T), length(L, 9), order(L, Pairs).
T = [86, 105, 120, 101, 110, 32, 115, 104, 111|...],
Pairs = [['Vixen', >, 'Rudolph'], ['Vixen', >, 'Prancer'], ['Vixen', >, 'Dasher'], ['Vixen', <
, 'Dancer'], ['Vixen', <, 'Comet'], ['Dancer', >, 'Donder'], ['Dancer', >|...], ['Dancer'|...]
, [...|...]|...],
L = ['Prancer', 'Cupid', 'Rudolph', 'Dasher', 'Blitzen', 'Vixen', 'Comet', 'Donder', 'Dancer']

One nice thing we can do with this grammar is that we can also generate the text from a list of constraints:

?- Pairs = [['Prancer', <, 'Cupid'], ['Cupid', <, 'Rudolph']], phrase(text(Pairs), T), string_codes(S, T).
Pairs = [['Prancer', <, 'Cupid'], ['Cupid', <, 'Rudolph']],
T = [80, 114, 97, 110, 99, 101, 114, 32, 115|...],
S = "Prancer should be in front of Cupid. Finally, Cupid should be in front of Rudolph." .