Prolog is an elegant abstraction. One of the points of abstractions is that they let us concentrate our optimization efforts in one place. Prolog benefits from many decades of research into how to make it work fast. When your problem does require a Prolog-shaped solution the most sensible thing to do is to use a highly optimized Prolog system instead of reinventing a naive algorithm yourself. Your "inelegant" solution will not be faster.

(This is also the problem with "I'll just quickly implement a Prolog-like DSL when I need it". Sometimes not a bad idea, but you have to be realistic. Your "lightweight" Prolog will be worse in every way compared to serious Prolog implementations).

I feel like an inefficient solution is inelegant by definition.

Nah - for example, AIXI is so inefficient that it's literally uncomputable, but it is beautiful.

That sounds intuitively right but breaks down when you ask “inefficient at what?”. Are you efficient with CPU cycles or efficient with human working memory?

Richard O'Keefe in The Craft of Prolog: "Elegance is not optional".