I think there'll be all manner of constraint and constraint-logic programming approaches that'd be amenable. I wish I had a great answer for you as "the best".
IMO, these "zebra puzzle"/"einstein puzzle" style problems are like a "hello world" for many related techniques. What's more, there are many languages that combine several of these techniques together so that you can easily pick and choose where appropriate.
If you were just wanting to compare against another related style, answer-set programming is one thing that comes to mind.
Like most things in programming, there is no "only way" to solve something, and certainly no one language (or DSL) to solve anything. You could solve it programmatically in C writing your own backtracker or state enumerator and a validation function for the rules (or block of code if you are like an old coworker that liked 10k SLOC C functions).
miniKanren, Prolog, and others let you write the rules more concisely (almost always) and clearly (most of the time, not everyone will write clear code and clarity is subjective) than that, though.
