On: Solving a Dungeons and Dragons riddle using Prolog

[_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 → _xgw]

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