Can you do Logic Programming in Scala?

No, you can't do it, unless you actually create a logic engine, which kind of defeats the whole purpose.

Furthermore, pattern matching itself is wholly unsuited for this, for many reasons. Consider, for instance, the basic query itself: path(1, 5, P). In Scala's pattern matching, 1, 5 and P are outputs. You can't provide an input that could be used to produce the output.

With Prolog, this is like, assuming that 1 and 5 are fixed, what possible values could P take on? That's just now how pattern matching works.

Edit: With Scala 2.10, pattern matching is now compiled to an intermediate operation like for-comprehensions are, and then the default translation is further optimized. However, it is possible to define your own class to handle pattern matching, and I have seen it used to implement prolog login -- though I can't find the link, sorry.

The traditional answer to your question would outline that logic variables cannot be directly modeled in a language that assumes everything to be a value.

There is, however, a relatively new approach to map logic variables to functional constructs. In the concrete case the close-to-Prolog logic language Curry curry is translated to Haskell. What is very unusual in this approach is that logic variables are modeled with lazyness. For more, see KiCS2: A new compiler from Curry to Haskell. Maybe lazy val could be used to this end.

Haskell and Functional Programming Languages have been the direct source of inspiration for Scala. One of the applications inherited from those languages is the development of Domain Specific Languages (DSLs). There are quite a few DSLs for Logic Programming (Prolog) in Haskell. It should be quite possible to port such a DSL library to Scala, if that has not happened yet.

See http://kanren.sourceforge.net/ for details on how functional and logic programming aren't really all that far apart. Stream structures are the key to understanding how the two paradigms can come together. By "lifting" standard functions into a stream/logic format, they can exhibit problem solving behavior that looks a lot like Prolog.

You should also look at parser combinators. With the right combinators in place, efficient Prolog-like solving capabilities are possible.