Most of these kinds of problems are only about 100 lines of code even in fairly verbose languages, depending on how complicated the set you need to permute / select from is, and how complicated your clauses are.
I speak from experience here, solving packing problems in programming competition questions. Pretty much any high school / college programming competition includes one of these kinds of problems, and the time budget is rarely a lot more than an hour, as it's usually one of the simpler questions.
I guess programming an open-ended system would have taken the 15-year-olds an extra 6-7 minutes.
What a lot of this ends up coming down to is the domain expertises of the code author. If you're uncomfortable with recursion, or writing simple interpreters, then Prolog is a much bigger win. Otherwise, it has a higher hurdle to climb.
Interpreters themselves are pretty trivial. Writing a parser and interpreter for a simple expression language (no control flow or anything like that, just a predicate possibly with some arguments) should by itself take no more than an hour. I know from past experience it takes me about 25 minutes, as it's one of the first things I do when I learn a new language.
Shame on me for being snarky.
In other words: an ad hoc, informally-specified, bug-ridden, slow implementation of half of Prolog.
I agree that Prolog would probably fare better as an embedded language like Lua, though - it's best suited to things like rules engines and parsers, rather than whole applications.